[프로그래머스 Lv.3] 섬 연결하기(Java) - MST, 프림과 크루스칼 두 가지 풀이

📌 핵심 요약

• 최소 신장 트리(MST) 문제 — 모든 섬을 사이클 없이 최소 비용으로 잇는다. 사용하는 다리는 정확히 n-1개다.
• 프림 — 방문한 섬 집합을 하나씩 키운다. 매번 "한쪽만 방문된 다리" 중 최저 비용을 고른다.
• 크루스칼 — 다리를 비용 오름차순으로 정렬한 뒤, 사이클을 만드는 다리만 건너뛴다.
• 사이클 판별은 유니온 파인드 — parent[a] == parent[b]가 아니라 find(a) == find(b)로 비교해야 한다.

 

목차

Programmers — 42861

섬 연결하기

n ≤ 100 · 간선 최대 4,950개

난이도: Level 3

n개의 섬과, 두 섬을 잇는 다리 목록 costs가 주어진다. costs[i] = [a, b, cost]는 a번 섬과 b번 섬을 cost 비용으로 이을 수 있다는 뜻이다. 모든 섬이 서로 오갈 수 있도록 다리를 놓을 때 드는 최소 비용을 구한다.

문제에서 읽어낸 조건

1. 모든 섬이 연결되기만 하면 되고, 두 섬 사이 경로가 여러 개일 필요는 없다.
2. 따라서 사이클을 만드는 다리는 비용만 늘릴 뿐 쓸모가 없다.
3. 섬 n개를 사이클 없이 전부 잇는 다리 수는 항상 n-1개다.

1 규모부터 확인했다

풀이를 고르기 전에 입력 규모를 먼저 봤다. n은 최대 100이고, 다리는 모든 섬 쌍을 이어도 100 × 99 / 2 = 4,950개다. 이 정도면 정렬을 하든, 매 반복마다 전체 간선을 훑든 시간이 남는다.

풀이	복잡도	실제 연산량(n=100 기준)	판정
프림(단순 구현)	O(n × E)	100 × 4,950 ≈ 495,000	여유
크루스칼	O(E log E)	4,950 × 12 ≈ 60,000	여유

둘 다 통과 범위 안이라 판단했고, 그래서 두 방식을 모두 구현해 봤다. 우선순위 큐 없이 배열만 쓰는 프림을 먼저 짰고, 이후 정석에 가까운 크루스칼을 다시 짰다.

2 프림 — 방문 집합을 한 칸씩 키운다

개념

프림은 연결된 덩어리 하나를 키워 나가는 방식이다. 0번 섬을 씨앗으로 삼고, 매 단계마다 "지금 덩어리에서 바깥으로 나가는 다리" 중 가장 싼 것을 골라 새 섬 하나를 끌어들인다. 이걸 n-1번 반복하면 모든 섬이 붙는다.

여기서 "바깥으로 나가는 다리"의 정의가 핵심이다. 다리 [from, to, cost]를 볼 때 판단해야 할 경우는 셋이다.

from 방문	to 방문	의미	후보 여부
O	O	둘 다 이미 덩어리 안 → 사이클	제외
X	X	덩어리와 닿지 않는 다리	제외
한쪽만 O		덩어리 → 새 섬으로 나가는 다리	후보

방문 여부만 boolean[] visited 하나로 관리하면 이 세 경우가 그대로 조건문으로 옮겨진다. 별도 자료구조가 필요 없다.

코드

 

Java — Solution.java (프림)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        boolean[] visited = new boolean[n];

        // 0번 섬부터 출발
        visited[0] = true;
        int connectedCount = 1;
        int totalCost = 0;

        // 모든 섬이 연결될 때까지 반복
        while (connectedCount < n) {
            int minCost = Integer.MAX_VALUE;
            int nextIsland = -1;

            // 이미 방문한 섬과 연결된 다리 중 최저 비용 다리 탐색
            for (int[] edge : costs) {
                int from = edge[0];
                int to   = edge[1];
                int cost = edge[2];

                // 한 쪽만 방문된 다리(새로운 섬으로 갈 수 있는 다리) 찾기
                if (visited[from] && !visited[to]) {
                    if (cost < minCost) {
                        minCost = cost;
                        nextIsland = to;
                    }
                } else if (!visited[from] && visited[to]) {
                    if (cost < minCost) {
                        minCost = cost;
                        nextIsland = from;
                    }
                }
            }

            // 가장 저렴한 다리로 새 섬 방문 처리
            if (nextIsland != -1) {
                visited[nextIsland] = true;
                totalCost += minCost;
                connectedCount++;
            }
        }
        return totalCost;
    }
}

동작 추적

입력을 n = 4, costs = [[0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8]]로 두고 visited 배열이 어떻게 변하는지 따라갔다.

반복	visited	후보 다리(한쪽만 방문)	선택	totalCost
시작	[T, F, F, F]	–	–	0
1회차	[T, F, F, F]	0-1(1), 0-2(2)	0-1, 비용 1	1
2회차	[T, T, F, F]	0-2(2), 1-2(5), 1-3(1)	1-3, 비용 1	2
3회차	[T, T, F, T]	0-2(2), 1-2(5), 2-3(8)	0-2, 비용 2	4
종료	[T, T, T, T]	connectedCount == n	–	4

2회차에서 1-2(비용 5)를 무시하고 1-3(비용 1)을 고른 부분이 이 방식의 성격을 보여준다. 어떤 섬을 다음에 붙일지는 정해두지 않고, 그 시점에 가장 싼 출구를 따라간다.

⚠️

무한 루프 가능성

nextIsland == -1이면 connectedCount가 늘지 않아 while이 영원히 돈다. 이 문제는 모든 섬을 연결할 수 있음이 보장되어 실제로 발생하지 않지만, 방어적으로 else break;를 붙여두는 편이 안전하다.

3 크루스칼 — 싼 다리부터 놓되 사이클만 피한다

개념

크루스칼은 순서를 뒤집는다. 덩어리를 키우는 게 아니라, 다리 전체를 비용 오름차순으로 정렬해두고 앞에서부터 훑는다. 각 다리에 대해 던지는 질문은 하나뿐이다.

"이 다리의 양 끝은 이미 같은 덩어리인가?"

같으면 놓아봐야 사이클이므로 버리고, 다르면 놓아서 두 덩어리를 합친다. 프림에서는 visited 하나로 덩어리가 딱 하나였지만, 크루스칼은 여러 덩어리가 동시에 자라다가 합쳐진다. 그래서 "방문했는가"가 아니라 "어느 덩어리에 속하는가"를 물어야 하고, 이 질문에 답하는 자료구조가 유니온 파인드다.

유니온 파인드

parent[i]는 i번 섬의 부모를 담는다. 대표가 아니라 부모다. 이 구분이 중요하다. 처음에는 모두 자기 자신이 부모이고, 이때는 각자가 곧 대표다.

find(x)는 부모를 계속 타고 올라가 parent[x] == x인 지점, 즉 대표를 찾는다. 그리고 돌아오는 길에 parent[x] = find(parent[x])로 결과를 다시 저장한다. 다음에 같은 섬을 물으면 한 번에 대표가 나온다. 이게 경로 압축이다.

union(0,1) → union(1,3) → union(0,2)를 차례로 실행했을 때 parent 배열의 변화는 다음과 같다.

시점	parent[0]	parent[1]	parent[2]	parent[3]	덩어리
초기	0	1	2	3	{0} {1} {2} {3}
union(0,1)	0	0	2	3	{0,1} {2} {3}
union(1,3)	0	0	2	0	{0,1,3} {2}
union(0,2)	0	0	0	0	{0,1,2,3}

union(1,3)에서 바뀐 칸이 parent[1]이 아니라 parent[3]인 데 주목했다. 1의 대표는 이미 0이므로, 합칠 때 손대야 하는 건 인자로 받은 1이 아니라 대표인 0이다. 그래서 union 내부는 parent[y] = x가 아니라 parent[find(y)] = find(x)여야 한다.

코드

 

Java — Solution.java (크루스칼)

import java.util.*;

class Solution {

    private int[] parent; // parent[i] = i의 부모 섬

    public int solution(int n, int[][] costs) {
        // 1) 비용 오름차순 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        // 2) 처음에는 모든 섬이 각자 하나의 덩어리
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int totalCost = 0;      // 누적 비용
        int usedEdgeCount = 0;  // 실제로 사용한 다리 수

        for (int[] edge : costs) {
            int islandA = edge[0];
            int islandB = edge[1];
            int cost    = edge[2];

            // 같은 덩어리면 사이클이므로 건너뛴다
            if (find(islandA) != find(islandB)) {
                union(islandA, islandB); // 연결
                totalCost += cost;       // 비용 누적
                usedEdgeCount++;

                // 다리 n-1개면 모든 섬이 연결된 상태
                if (usedEdgeCount == n - 1) break;
            }
        }
        return totalCost;
    }

    /** x가 속한 덩어리의 대표를 찾는다 (경로 압축) */
    private int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    /** 두 덩어리를 하나로 합친다 */
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
}

동작 추적

같은 입력을 정렬하면 [0,1,1] → [1,3,1] → [0,2,2] → [1,2,5] → [2,3,8] 순이 된다.

다리	find(A)	find(B)	판정	totalCost
0-1 (1)	0	1	연결	1
1-3 (1)	0	3	연결	2
0-2 (2)	0	2	연결 → 3개 도달, 종료	4
1-2 (5)	0	0	사이클	–
2-3 (8)	0	0	사이클	–

프림과 고른 다리 집합이 같고 합계도 4로 일치한다. 다만 고르는 순서는 다르다. 프림은 0-1 → 1-3 → 0-2를 "덩어리에서 가까운 순"으로 골랐고, 크루스칼은 "전체에서 싼 순"으로 골랐다. 이 문제처럼 MST가 하나로 정해지는 경우 결과는 같다.

4 두 풀이 비교

구분	프림	크루스칼
기준	정점(섬)을 하나씩 흡수	간선(다리)을 싼 순으로 채택
덩어리 수	항상 1개	여러 개가 자라다 합쳐짐
필요한 자료구조	boolean[] visited	유니온 파인드 + 정렬
제외 판정	양쪽 다 방문 → 건너뜀	find(a) == find(b) → 건너뜀
복잡도	O(n × E)	O(E log E)
코드 길이	짧음	보조 메서드 2개 필요
확장성	간선이 많을수록 불리	간선 수에만 비례

💡

어느 쪽을 고를까

간선이 정점 수에 비해 촘촘하면 프림(우선순위 큐 버전)이, 성기면 크루스칼이 유리하다. 다만 이 문제는 n이 100이라 어느 쪽이든 통과한다. 유니온 파인드를 손에 익히려는 목적이면 크루스칼로 푸는 편이 남는 게 많다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.