BOJ (Java) 1197번: 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

---

풀이

주어진 그래프의 모든 정점들을 연결하며, 그 가중치의 합이 최소인 트리를 구해야 한다.

이 때 트리이므로 루프가 생기면 안 된다.

따라서 크루스칼 알고리즘을 사용, 가중치가 적은 것부터 연결한다.

이 때 연결 여부를 확인 후 연결해야 하므로 union-find 를 사용하여 확인한다.

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    private static int[] group;
    private static int V, E;
    public static void main(String[] args) throws IOException {
        
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");
        V = Integer.parseInt(inputs[0]);
        E = Integer.parseInt(inputs[1]);
        group = new int[V];

        for (int i = 0; i < V; i++) {
            group[i] = i;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(a[2], b[2])
        );
        for (int i = 0; i < E; i++) {
            inputs = bf.readLine().split(" ");
            int A = Integer.parseInt(inputs[0]) - 1;
            int B = Integer.parseInt(inputs[1]) - 1;
            int C = Integer.parseInt(inputs[2]);
            pq.add(new int[]{A, B, C});
        }

        // 크루스칼 알고리즘, 가중치가 작은 것부터 탐색
        long sum = 0;
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            if (find(now[0]) == find(now[1])) continue;

            union(now[0], now[1]);
            sum += now[2];
        }

        System.out.println(sum);
    }

    // 현재 속해 있는 집합 확인
    private static int find(int a) {
        if (group[a] == a) {
            return a;
        }
        return group[a] = find(group[a]);
    }

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            group[rootB] = rootA;
        }
    }
}