11. 최소 신장 트리(MST): 크루스칼 알고리즘(Kruskal's Algorithm)

최소 신장 트리 혹은 최소 스패닝 트리라고 불리는 MST(Minimum Spanning Tree)는 가중치가 포함된 무향의 그래프가 주어졌을 때, 모든 노드들이 포함되면서 비용은 최소가 되는 부분 그래프인 트리를 의미합니다. 이와 같은 조건을 만족하는 MST를 찾기위해 크루스칼 알고리즘(Kruskal's Algorithm)이나 프림 알고리즘(Prim's algorithm)을 사용합니다. 이 두가지 알고리즘은 동일한 시간복잡도를 갖고 있기 때문에 어느 알고리즘이 더 우월하다고 할 수 없으나, 크루스칼 알고리즘은 간선을 기준으로 구현되고, 프림 알고리즘은 노드 기준으로 알고리즘이 구현된다는 부분에서 차이를 갖고 있습니다. 이번에는 간선을 기준으로 한 크루스칼 알고리즘을 설명해보도록 하겠습니다.

크루스칼 알고리즘을 학습하기에 앞서 유니온 파인드 알고리즘에 대해 확실하게 이해하고 있는지 확인해보시기 바랍니다. 크루스칼 알고리즘은 유니온 파인드 알고리즘이 기본이 되는 알고리즘입니다. MST의 정의에서 확인하였듯이 최종적으로 답이 되는 그래프에는 모든 노드들이 포함되어 있어야합니다. 노드들의 연결관계를 알려주는 것이 바로 유니온 파인드 알고리즘이고, 이를 통해 우리는 연결되지 않을 노드들을확인해가면서 모든 노드들이 그래프에 편입되도록 소스를 구현할 수 있습니다. MST의 정의에서 나오는 모든 노드들이 포함되면서 부분을 유니온 파인드로 해결했다면, 비용이 최소가 되도록 하는 부분은 Heap을 사용하여 해결합니다. Heap을 사용하되 가장 작은 비용값을 갖고 있는 간선 정보가 제일 앞에 오도록 구현합니다. 실제 문제를 풀 때는 우선순위 큐(Priority Queue)를 사용하여 구현할 것입니다. Heap과 유니온 파인드의 컴비네이션으로 크루스칼 알고리즘이 구현됩니다.

구체적으로 로직이 어떻게 구현되야하는지 알아보겠습니다. 일단 유니온 파인드 알고리즘과 동일한 형식의 그래프 구조를 소스로 구현합니다. 그다음 우선순위 큐를 하나 선언하되 비용을 기준으로 더 작은 비용이 먼저 poll될 수 있도록 Comparator를 구성해줍니다. 그리고 양 끝의 노드 정보와 비용 정보를 큐에 넣어줍니다. 큐에 들어갈 때마다 비용이 더 적은 간선 정보가 더 먼저 나오도록 정렬이 일어납니다. 그다음 간선정보가 들어있는 큐에서 하나씩 값을 빼주면서 간선의 양끝 노드가 같은 루트노드를 공유하고 있는지 확인하여 만일 같은 노드를 바라보고 있다면 그냥 넘어가고 다른 노드를 바라보고 있다면 서로 연결되지 않았다는 뜻이므로 유니온시키면서 비용을 기록합니다. 그렇게 큐가 빌 때까지 모든 간선정보를 확인해주면 모든 노드들이 포함된 최소 비용의 부분 그래프를 구할 수 있습니다.

실제 문제를 풀이해보면서 살펴보겠습니다.

1197번: 최소 스패닝 트리 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
class Main {
    private static int[] par;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine().trim());
 
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
 
        par = new int[V + 1];
        for (int i = 1; i <= V; i++)
            par[i] = i;
 
        Edge[] edge = new Edge[E];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            edge[i] = new Edge(s, e, c);
        }
 
        Arrays.sort(edge, new Comparator<Edge>() {
            public int compare(Edge e1, Edge e2) {
                return e1.c - e2.c;
            }
        });
 
        int ans = 0;
        for (int i = 0; i < E; i++) {
            int p = find(edge[i].s);
            int q = find(edge[i].e);
 
            if (p == q)
                continue;
            par[q] = p;
            ans += edge[i].c;
        }
 
        System.out.println(ans);
    }
 
    private static int find(int n) {
        if (par[n] == n)
            return n;
        return par[n] = find(par[n]);
    }
 
}
 
class Edge {
    int s;
    int e;
    int c;
 
    Edge(int s, int e, int c) {
        this.s = s;
        this.e = e;
        this.c = c;
    }
}