[프로그래머스] 섬 연결하기 / Prim & Kruskal 알고리즘 풀이

 

이 문제는 MST(최소 신장 트리)이다. MST인지 알아보는 근거는 아래와 같다.

🔎 MST 문제의 전형적인 특징

1. 여러 개의 정점(섬, 도시, 컴퓨터, 송전탑 …) 이 있고
2. 정점들을 연결하는 간선(다리, 도로, 케이블, 전선 …) 들이 주어지며
3. 각 간선마다 비용(길이, 공사비, 연결비, 전력량 …) 이 있음
4. 모든 정점을 연결해야 하는데
5. 총 비용이 최소가 되어야 함

🔹 MST (최소 신장 트리)에서의 Greedy 알고리즘

MST 문제를 풀 때 가장 대표적으로 쓰이는 Greedy 알고리즘은 Prim과 Kruskal 두 가지이다.

1. Prim 알고리즘
   • 아이디어: “시작 노드에서 출발해 가장 작은 간선만 선택하며 MST를 확장”
   • 구현 특징:
     • 보통 Priority Queue(최소 힙) 사용 → 가장 작은 간선을 빠르게 찾기 위해
     • 인접 리스트 + 우선순위 큐 → 시간복잡도 O(E log V)
   • 직관적으로는 “점 중심으로 확장”
2. Kruskal 알고리즘

• 아이디어: “전체 간선을 비용순으로 정렬 후, 사이클 없는 간선만 채택 (Union-Find 활용)”
• 구현 특징:
  • Union-Find(Disjoint Set Union) 사용 → 사이클 여부 판별
  • 간선 정렬 때문에 O(E log E) (≈ O(E log V))
• 직관적으로는 “간선 비용이 가장 적은 것 부터 선택”

Prim 알고리즘 풀이

1. 임의의 노드에서 시작 → MST에 추가
2. MST에 포함된 노드와 MST에 없는 노드를 연결하는 간선 중 최소 비용 선택
3. 선택한 간선을 MST에 추가하고, 그 노드도 MST에 포함
4. 모든 노드가 MST에 포함될 때까지 반복

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        // 각 노드별로 연결된 간선 리스트 저장
        List<List<int[]>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for(int[] edge : costs) {
            int a = edge[0], b = edge[1], cost = edge[2];
            graph.get(a).add(new int[]{b, cost});
            graph.get(b).add(new int[]{a, cost});
        }

        boolean[] visited = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        int totalCost = 0;
        pq.offer(new int[]{0, 0}); // 시작 노드 0, 비용 0

        while(!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0], cost = curr[1];

            if(visited[node]) continue;
            visited[node] = true;
            totalCost += cost;

            for(int[] next : graph.get(node)) {
                if(!visited[next[0]]) {
                    pq.offer(new int[]{next[0], next[1]});
                }
            }
        }

        return totalCost;
    }
}

 

Kruskal 알고리즘 풀이

1. 모든 간선을 비용 오름차순으로 정렬
2. 간선을 하나씩 확인하며 사이클이 생기지 않는 경우 MST에 추가
3. Union-Find를 이용해 두 노드가 같은 집합인지 확인 → 사이클 체크
4. MST 완성 시 모든 노드 연결

import java.util.*;

class Solution {
    int[] connected = new int[101];
    public int solution(int n, int[][] costs) {
        int totalCost = 0;
        
        Arrays.sort(costs, (c1, c2) -> c1[2] - c2[2]);
        
        for(int i = 0; i < 101; i++) {
            connected[i] = i;
        }
        
        for(int[] edge : costs) {
            int a = edge[0], b = edge[1], cost = edge[2];
            if(find(a) == find(b)) continue;
            
            union(a, b);
            totalCost += cost;
        }
        return totalCost;
    }
    
    int find(int i) {
        if (connected[i] == i) return i;
        return connected[i] = find(connected[i]);
    }
    
    void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if(rootI != rootJ) {
            connected[rootJ] = rootI; // j의 루트를 i 루트에 붙임
        }
    }
}