[TAVE/이코테] ch10 그래프 이론 | 실전 문제

참고자료: 이것이 코딩테스트다

 

2. 실전 - 팀 결성

---

team_count, calculation = map(int, input().split())
parent = [0] * (team_count + 1) #[0, 0, 0, 0, 0, 0, 0, 0]

#각 num번 팀에 num번 학생을 속하게 한다.
for num in range(team_count + 1): #[0, 1, 2, 3, 4, 5, 6, 7]
    parent[num] = num

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]

for _ in range(calculation):
    cal, student1, student2 = map(int, input().split())
    if cal:
        student1 = find_parent(parent, student1)
        student2 = find_parent(parent, student2)
        if student1 == student2:
            print('YES', end = " ")
        else:
            print('NO', end = " ")
    else:
        student1 = find_parent(parent, student1)
        student2 = find_parent(parent, student2)
        if student1 < student2:
            parent[student2] = student1
        else:
            parent[student1] = student2

👉🏻책의 풀이를 참고했다.

 

3. 실전 - 도시 분할 계획

---

house_count, path_count = map(int, input().split())
parent = [0] * (house_count + 1)
edges = []
result = 0
higest_cost = 0

for i in range(1, house_count + 1):
    parent[i] = i

for _ in range(path_count):
    house1, house2, cost = map(int, input().split())
    edges.append((cost, house1, house2))

edges.sort()

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    if find_parent(parent, a) < find_parent(parent, b):
        parent[b] = a
    else:
        parent[a] = b


for edge in edges:
    cost, house1, house2 = edge
    if find_parent(parent, house1) != find_parent(parent, house2): #같은 집합 x
        union_parent(parent, house1, house2)
        result += cost
        if higest_cost < cost:
            higest_cost = cost

print(result - higest_cost)
print(result, higest_cost)

👉🏻이 문제는 2개의 최소 신장 트리를 만들어야 한다. 최소한의 비용으로 2개를 만들기 위해서는 신장트리를 먼저 찾은 뒤에 비용이 가장 큰 간선을 제거하면 된다.

✍🏻풀었는데 출력이 8이 아닌 14가 나오는 상황... 먼일이지

🐰맨 앞에 동물원에서 탈출한 원숭이 얘기는 왜 나온 건지 너무 궁금하다.ㅋㅋㅋㅋ