[이코테] 09. 그래프 이론 - 도시 분할 계획

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

---

문제

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있다. 또한 길마다 길을 유지하는 데 드는 유지비가 있다.

마을의 이장은 마을이 너무 커서 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.

즉 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 하고, 마을에는 집이 하나 이상 있어야 한다.

분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.

마을의 이장은 위의 조건을 모두 만족하면서, 길들을 모두 없애고 길의 유지비의 합을 최소로 하고 싶다.

 

입력 조건

• 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상, 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.
• 그다음 줄부터 M 줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어진다. A번 집과 B번 집을 연결하는 길의 유지비가 C(1 ≤ C ≤ 1,000)라는 뜻이다.

출력 조건

• 첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.

 

입력 예시
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

출력 예시
8

---

나의 풀이

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


def union(parent, x, y):
    x = find_parent(parent, x)
    y = find_parent(parent, y)

    if x < y:
        parent[y] = x
    else:
        parent[x] = y


N, M = map(int, input().split())
parent = list(range(N+1))

edges = []

for _ in range(M):
    # A -> B : C
    A, B, C = map(int, input().split())
    edges.append((C, A, B))

# 비용 기준 정렬
edges.sort()
result = []

for cost, a, b in edges:
    # 사이클이 발생하지 않으면 == 루트 노드가 다르면 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        result.append(cost)

# 맨 마지막 cost 제외
print(sum(result[:N-2]))

---

해설

이 문제는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다.

최소한의 비용으로 2개의 신장 트리로 분할하려면 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 그중 가장 비용이 큰 간선을 제거한다. 그러면 최소 신장 트리가 2개의 부분 그래프로 나누어진다.

---