백준 - 1197 최소 스패닝 트리(Java)

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

1197번: 최소 스패닝 트리

 

크루스칼(Kruskal) 문제입니다.

시점이 없고, 최소 스패닝 트리를 구하는 문제이기 때문에 크루스칼 알고리즘을 사용해야 한 다는 것을 알 수 있습니다.

최소 스패닝 트리란, 사이클 없이 모든 노드를 연결할 때 가중치의 합이 최소가 되도록 만드는 트리입니다.

 

크루스칼 알고리즘은 기본적으로 유니온-파인드(Union-Find)를 사용합니다.

혹시, 유니온-파인드 알고리즘을 잘 모르시는분들은 https://ksb-dev.tistory.com/114를 참고하시면 됩니다.

 

크루스칼은 프림과 달리 시점 없이 간선이 최소인 스패닝 트리를 만드는 것이기 때문에, 가중치를 바탕으로 정렬이 필요합니다.

정렬된 간선을 가장 작은것 부터 하나씩 사용해서 사이클이 발생하지 않도록 만들기 위해 유니온-파인드가 필요한 것입니다.

다들 아시다 싶이, 유니온-파인드는 서로 다른 두 개의 노드가 같은 집합에 있는지 판단하고, 두 개의 노드를 연결할 수 있습니다.

이 특성을 이용하면 사이클이 발생하지 않도록 노드들을 연결해 최소 스패닝 트리를 만들 수 있습니다.

가중치가 가장 작은것 부터 연결을 하는데, 만일 두 노드가 이미 연결되어 있다면 현재 간선은 스킵하면 됩니다.

만약 스킵하지 않고 연결하게 된다면 이미 연결된 노드를 한번 더 연결하기 때문에 사이클이 발생합니다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {
    private static int v, e;
    private static List<Node> graph;
    private static int[] parents;

    private static class Node implements Comparable<Node> {
        int s, e, w;

        Node(int s, int e, int w) {
            this.s = s;
            this.e = e;
            this.w = w;
        }

        // 오름차순 정렬
        @Override
        public int compareTo(Node o) {
            return this.w - o.w;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        v = Integer.parseInt(stz.nextToken());
        e = Integer.parseInt(stz.nextToken());

        parents = new int[v + 1];
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < e; i++) {
            stz = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

            graph.add(new Node(a, b, c));
        }

        // 가중치 오름차순 정렬
        Collections.sort(graph);

        // 가중치가 작은 간선부터 사용
        // union연산을 통해 같은 집합에 있지 않으면 연결시킴
        long edge = 0;
        for (Node node : graph) {
            if (!union(node.s, node.e)) {
                edge += node.w;
            }
        }

        bw.write(String.valueOf(edge));

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean union(int x1, int x2) {
        int x1Root = find(x1);
        int x2Root = find(x2);

        if(x1Root != x2Root) {
            if (x2Root > x1Root) {
                parents[x1Root] = x2Root;
            } else{
                parents[x2Root] = x1Root;
            }
            return false;
        }
        return true;
    }

    private static int find(int num) {
        if (parents[num] == num) {
            return num;
        }
        return find(parents[num]);
    }
}