[알고리즘] 최소 신장 트리 (MST) (feat. kruskal, Prim 알고리즘)

 

최소 신장 트리 (MST: Minimum Spanning Tree)

그래프에서 모든 정점을 포함하고 사이클이 없으며, 총 간선 비용이 최소인 트리

MST의 핵심 특징

1. 간선은 정확히 n - 1개
2. 사이클이 없음
3. 모든 노드 연결
4. 총 비용 최소

 

MST를 구하는 대표 알고리즘 2개

알고리즘의 공동목표

모든 정점을 최소 비용으로 사이클 없이 연결하자
즉, 최소 신장 트리 만들기

1️⃣ Kruskal 알고리즘

"간선을 비용 기준으로 정렬해서 가장 싼 것부터 고르자"

• 간선 비용(cost) 기준 오름차순 정렬
• 작은 것부터 선택
• 사이클 생기면 건너뜀
• Union - Find 사용
• 시간복잡도는 O(E log E)

과정

1. 모든 간선을 비용 기준 오름차순 정렬
2. 가장 작은 간선부터 하나씩 선택
3. 사이클이 생기면 버림
4. 간선이 V-1개가 되면 종료

2️⃣ Prim 알고리즘

"현재 연결된 노드에서 가장 싼 간선을 하나씩 확장하자"

• 한 노드에서 시작
• 현재 연결된 노드 집합에서 가장 비용이 작은 간선 선택
• 우선순위 큐 사용
• 시간복잡도는 O(E log V)

과정

1. 아무 노드에서 시작
2. 연결 가능한 간선 중 최소 비용 선택
3. 새로운 노드를 트리에 포함
4. 모든 노드 포함될 때까지 반복

Kruskal 알고리즘 활용 문제

백준 섬 연결하기 - 42861 번

import java.util.*;

class Solution {
    static int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 비용 순으로 정렬하기
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        
        for (int[] edge: costs) {
            int u = edge[0];
            int v = edge[1];
            int cost = edge[2];
            
            // 사이클이 아닌지 확인
            if (find(u) != find(v)) {
                union(u, v);
                answer += cost;
            }
        }
        
        return answer;
    }
    
    // 같은 팀인지 확인
    private int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 경로 압축하기
    }
    
    // 같은 팀으로 만들기
    private void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) parent[pb] = pa;
    }
}