[백준 1647] 도시 분할 계획

문제

어떤 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져있다. 각 길은 유지비가 들고있으며 마을을 두 개의 마을로 분할할 계획을 갖고있다. 

마을에는 집이 하나 이상 있어야하고 분리된 두 마을 사이에 있는 길들도 필요없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있을 때 나머지 길 유지비의 합을 최소로 되도록 하라.

 

입력

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

 

출력

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

---

접근

분리된 마을에서 각 마을은 하나 이상의 집이 무조건 있어야한다. 그리고 분리된 마을은 연결할 필요가 없다. 그리고 나머지 길을 최소로 해야하기 때문에 N개의 마을의 최소 신장 트리를 구한다. 하지만 마을을 두 개로 분리해야하기 때문에 N-2개의 간선을 선택하는 크루스칼 알고리즘을 적용한다.

 

기존에 N-1개의 간선을 선택하는 것은 모든 집을 연결할 때의 최소 신장 트리가 아닌 N-2개를 선택하여 한 개의 집은 연결이 안되도록 한다.

 

구현

- 그래프를 입력받고 비용을 기준으로 오름차순 정렬한다.

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph.append((a, b, c))

graph = sorted(graph, key=lambda x: x[2])

 

- a집과 b집의 루트 노드가 다를 때 두 집을 연결하며 연결한 간선의 수가 N-2개 일때 종료한다.

- N-2개를 선택했을 때가 최소 비용으로 마을을 분리하는 경우이다.

edge_count = 0
answer = 0

for a, b, c in graph:
    if find_set(a) != find_set(b):
        union(a, b)
        edge_count += 1
        answer += c

    if edge_count == N-2:
        break

---

전체 코드

import sys
input = sys.stdin.readline

def find_set(a):
    if p[a] == a:
        return a
    else:
        b = find_set(p[a])
        p[a] = b
        return b

def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        p[b] = a

N, M = map(int, input().split())
p = [n for n in range(N)]
graph = []
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph.append((a, b, c))

graph = sorted(graph, key=lambda x: x[2])

edge_count = 0
answer = 0

for a, b, c in graph:
    if find_set(a) != find_set(b):
        union(a, b)
        edge_count += 1
        answer += c

    if edge_count == N-2:
        break

print(answer)