[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)

최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST 알고리즘에 대해서 정리해볼까 합니다.

정리하려는 주된 내용은 아래와 같습니다.

❓ MST가 무엇인지, 크루스칼 알고리즘의 구현 및 동작 방식

 

📑 MST란?

MST는 Minimum Spanning Tree의 약자로 최소 신장 트리를 찾기 위한 알고리즘입니다.

또한 Spanning Tree(신장 트리)는 간단하게 설명하면 모든 정점을 포함하면서 사이클이 없는 연결 그래프를 의미합니다.

왜 사이클이 없어야할까❓ (25.06.21 추가)

처음에는 모든 정점이 연결만 되면 된다고 생각했습니다. (이 과정에서 사이클이 생기든 말든지요.)

그러나 MST 또한 트리이며, 트리 특성을 생각해보면 사이클이 없어야 합니다.

트리에서 한 정점에서 다른 정점으로 가는길은 한 개로 유일해야 하거든요.

 

참고로 트리에서 사이클이 발생하면 트리가 아닌, 단순한 연결 그래프가 됩니다.

 

일반 신장트리와 최소 신장 트리는 아래 이미지를 참고해주세요.

다른 방식의 연결 방식이 있을 수 있습니다. 참고만 해주세요.

두 연결 그래프 모두 사이클(Cycle)이 없습니다. 또한 모든 정점을 포함하고 있습니다.

모두 신장 트리이지만, 오른쪽 신장 트리의 가중치 합이 제일 최소가 됩니다.

MST 알고리즘은 이렇게 만들 수 있는 모든 신장 트리(Spanning Tree) 중 가중치 합이 최소가 되는 신장 트리를 효율적으로 탐색하는 알고리즘입니다.

 

✅크루스칼 알고리즘 (Kruskal Algorythm)

위와 같은 MST를 찾는 방식에는 대표적으로 크루스칼, 프림 두 가지 방식이 있습니다.

이번 포스팅에서는 크루스칼 방식에 대해서 정리하려 합니다.

 

크루스칼 알고리즘을 구현하기 위해서는 Union-Find 알고리즘에 대한 배경지식이 있어야 합니다.

해당 알고리즘은 이미 정리해둔 포스팅이 있기에 아래에 링크만 첨부하도록 하겠습니다.

[알고리즘] Union-Find (부제 : 좌표 압축은 왜?)

[알고리즘] Union-Find (부제 : 좌표 압축은 왜?)

 

크루스칼은 그리디 알고리즘이기도 합니다.

이유는 MST를 찾기 위한 방식이 그리디와 비슷하게 모든 간선들에 대해서 최소 비용의 간선들만 연결해가며 MST를 탐색하는 방식이기 때문입니다.

 

🕹️ 동작 과정

앞서 최소 비용의 간선들만 연결한다고 설명드렸는데요.

이를 위해서 우선 모든 간선들에 대해서 가중치를 기준으로 오름차순 정렬을 수행합니다.

 

정렬된 간선들에 대해서 연결을 하는데 다음과 같은 부분을 주의해야 합니다.

⚠️ 해당 간선을 연결하면 사이클이 생기는가?

이 부분을 해결하기 위해 크루스칼에서 Union-Find 알고리즘을 사용합니다.

또한 저의 경우에는 불필요한 간선이 연결될 수도 있다는 생각을 했었습니다.

예를 들어 임의의 두 정점이 다른 정점들과 연결이 되었음에도, 두 정점 사이의 간선이 최소 비용이기 때문에 불필요하게 연결되는 경우가 발생할 수 있지 않을까?

그러나 이 경우도 마찬가지로 사이클이 발생하기 때문에 Union-Find만 사용한다면 상관없습니다.

 

🔎 구현 방식

기본적으로 구현은 Union-Find 알고리즘만 숙지하고 계신다면 굉장히 간단합니다.

왜냐하면 간선들에 대해 비용을 기준으로 정렬만 수행하면 되기 때문입니다.

 

이번에 풀이했던 문제를 기준으로 설명을 드리겠습니다.

백준의 행성 연결이라는 문제입니다. (골드 4)

BOJ_16398 행성 연결

 

위 문제에서는 "제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자"가 주요 키워드인데요.

MST 문제는 위처럼 모든 OO을 연결하기 위한 최소 비용을 구하자 라는 공통적인 언급이 있습니다.

 

아래는 해당 문제를 풀이했던 소스코드입니다.

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

//BOJ_16398
public class Main {
    static class Node {
        int x;
        int y;
        int w;
        public Node(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    static int n;
    static long res;
    static int[] parent;
    static List<Node> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                list.add(new Node(i,j,Integer.parseInt(st.nextToken())));
            }
        }
        
        // TODO : 가중치를 기준으로 오름차순 정렬
        Collections.sort(list, (o1, o2) -> o1.w - o2.w);

        parent = new int[n];
        for(int i=0; i<n; i++) parent[i] = i;

        // TODO : 연결할 수 있는 간선이라면 비용 추가
        for(Node cur : list) {
            if(!union(cur.x, cur.y)) continue;
            res += cur.w;
        }

        System.out.println(res);

    }

    static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if(aRoot == bRoot) return false;
        parent[bRoot] = aRoot;

        return true;
    }
}

 

코드를 보시면 알겠지만 Union-Find를 제외하고는 간선을 정렬하기 위한 로직밖에 없습니다.

조금 다른 점은 같은 부모를 가진 두 정점의 경우에는 boolean 결과를 통해 SKIP하고, 다른 부모를 가진 경우에만 결과값에 가중치를 더하는 부분입니다.

 

또한 정렬하기 위한 방식으로는 List를 사용해도 되고, 배열 혹은 우선순위 큐를 사용해도 상관없습니다. (시간복잡도 차이는 아래 이미지를 참고해주세요.)

객체 참조 방식으로 구현을 해서 그런지 확실히 Arrays.sort()가 많이 느리네요.

 

#️⃣ 이후에는 다른 MST 알고리즘인 프림 알고리즘에 대해서도 정리하고, 크루스칼과는 어떻게 다른지 정리하려 합니다.

[JAVA] 프림 알고리즘 (+ 크루스칼과는 어떻게 다를까?) //25.06.21 추가

[JAVA] 프림 알고리즘 (Prim Algorythm)