문제 42
최소 스패닝 트리
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 가중치 간선으로 이루어진 연결된 무방향 그래프가 있다.
모든 정점을 연결하기 위해 선택한 간선의 가중치 합의 최솟값을 구하라.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; N-1 \le M \le 200\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 간선의 양 끝 정점의 번호와 가중치를 의미하는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^9)$
같은 두 정점을 연결하는 간선은 두 번 이상 주어지지 않는다.
주어지는 그래프는 항상 연결되어 있다.
출력
모든 정점을 연결하기 위해 선택한 간선의 가중치 합의 최솟값을 출력한다.
예제 입력 1
4 5 1 2 1 1 3 4 2 3 2 2 4 5 3 4 3
예제 출력 1
6
예제 입력 2
1 0
예제 출력 2
0
공식 해설
가벼운 간선부터 연결하기
가중치가 모두 양수이므로 선택한 간선에 사이클이 있다면 간선 하나를 빼도 연결을 유지하면서 비용을 줄일 수 있다. 따라서 최적해는 모든 정점을 잇는 트리이다.
크루스칼 알고리즘으로 간선을 가중치순으로 살펴본다. 양 끝점이 서로 다른 연결 요소에 있으면 간선을 고르고 두 요소를 합친다. 이미 같은 요소라면 사이클이 생기므로 건너뛴다. 연결 요소는 경로 압축과 크기 기준 합치기를 적용한 DSU로 관리한다.
현재 선택이 최적해를 막지 않는 이유
지금까지 고른 간선을 모두 포함하는 최소 스패닝 트리가 있다고 하자. 다음에 고를 간선 $e$가 그 트리에 없다면 $e$를 넣었을 때 사이클이 생긴다. 이 사이클에는 현재 서로 다른 연결 요소를 잇는 다른 간선 $f$가 있다.
$f$가 $e$보다 가벼웠다면 이미 검사했을 때 연결 요소들을 합쳤어야 하므로 $f$의 가중치는 $e$ 이상이다. 따라서 $f$를 $e$로 바꾸어도 비용은 늘지 않는다. 현재 선택을 포함하는 최적 트리가 계속 존재하므로 알고리즘은 최적이다.
연결된 그래프이므로 $N-1$개 간선을 고르면 끝난다. $N=1$이면 답은 $0$이다. 선택한 가중치의 합은 $(N-1)\cdot10^9$까지 커질 수 있다.
시간복잡도는 $O(N+M\log(M+1)+M\alpha(N))$, 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
간선들을 구조체 배열에 저장하고 가중치 기준 sort를 수행한다. DSU는 부모와 크기 배열로 구현하고, 두 대표가 다를 때만 간선 가중치를 long long 답에 더한다. 선택한 간선 수가 $N-1$이면 종료한다.
C 구현
간선 구조체를 가중치 순으로 qsort하고 DSU로 두 루트가 다를 때만 선택한다. 가중치 합은 최대 약 $10^{14}$이므로 long long으로 둔다. 비교 함수의 반환값에 long long 차이를 int로 잘라 넣지 않는다.
Python 구현
(w,u,v) 튜플을 정렬하고 반복문 find와 크기 기준 union을 사용한다. 선택한 간선의 합은 Python int로 누적한다. N-1개를 선택하면 나머지 간선을 처리할 필요가 없다.
Java 구현
간선을 가중치로 정렬하고 int[] DSU를 사용한다. 합은 long으로 계산한다. 비교에는 Integer.compare나 comparingInt를 사용하고 가중치 차를 반환하는 방식은 피한다.
Rust 구현
(가중치,u,v) 튜플을 sort_unstable()하고 DSU로 사이클을 제외한다. 간선 가중치는 i32로 저장해도 합은 i64로 누적한다. DSU find는 반복문으로 구현할 수 있다.
JavaScript 구현
간선 배열은 가중치 비교 함수로 정렬하고 Int32Array 부모·크기로 DSU를 구성한다. find를 반복문과 경로 압축으로 작성해 깊은 재귀를 피한다.
총가중치는 $(N-1)\cdot10^9<10^{14}$이므로 Number로 정확하다. 정점 번호만 32비트 배열에 저장하고 답에 |0을 적용하지 않는다. 서로 다른 대표를 합쳤을 때만 가중치를 더하고 선택 수가 $N-1$이면 끝낸다. $N=1$에서는 처음부터 답이 $0$이다.