[MST] 프로그래머스 - 섬 연결하기 (Java)

ALGORITHM

최소 신장 트리(MST)의 정의와 성질, 그리고 이를 구하는 두 알고리즘인 크루스칼과 프림을 정리

1. MST(최소 신장 트리)

신장 트리(Spanning Tree)

그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프 트리의 정의를 그래프 전체 정점에 확장한 형태

신장 트리의 조건

• 정점 V개를 모두 포함
• 간선은 정확히 V-1개
• 사이클 없음
• 모든 정점이 연결(연결 그래프)

간선 V-1개, 사이클 없음, 연결됨. 이 셋 중 두 개가 성립하면 나머지 하나는 자동 성립. 트리의 기본 성질이며 MST 문제의 종료 조건으로 직결됨

최소 신장 트리

가능한 신장 트리 중 간선 가중치의 총합이 최소인 것

핵심 성질

• 간선 개수는 항상 V-1개로 고정
• MST는 유일하지 않을 수 있음. 동일 가중치 간선이 존재하면 여러 개 가능
• 모든 간선 가중치가 서로 다르면 MST는 유일
• 가중치 총합은 어떤 MST를 구하든 동일

정당성의 근거: Cut Property

그래프의 정점을 두 그룹으로 나눈 것을 컷(Cut)이라 함. 두 그룹을 가로지르는 간선을 교차 간선(Crossing Edge)이라 함

Cut Property

임의의 컷에 대해, 교차 간선 중 가중치가 가장 작은 간선은 반드시 어떤 MST에 포함됨

Cycle Property

사이클 안에서 가중치가 가장 큰 간선은 MST에 포함되지 않음

크루스칼과 프림은 이 두 성질을 서로 다른 방향에서 적용한 것 크루스칼은 사이클을 만들지 않는 최소 간선을 계속 고르고, 프림은 현재 덩어리라는 컷의 최소 교차 간선을 계속 고름. 결과적으로 같은 총합에 도달

MST와 최단 경로의 차이

둘 다 우선순위큐를 쓰고 구조가 비슷해 혼동하기 쉬우나 목적이 다름

구분	MST(프림)	최단 경로(다익스트라)
목적	전체 간선 가중치 합 최소화	시작점에서 각 정점까지 거리 최소화
큐에 넣는 값	간선 하나의 가중치	시작점부터의 누적 거리
시작점 영향	없음, 총합 동일	있음, 시작점이 곧 기준
결과물	트리 1개	거리 배열 dist[]
결과 관계	MST 경로가 두 점 간 최단 경로를 보장하지 않음	최단 경로 트리가 MST를 보장하지 않음

2. 크루스칼(Kruskal)

간선 중심 접근. 전체 간선을 가중치 오름차순으로 정렬한 뒤 싼 것부터 채택하되, 사이클을 만드는 간선은 버림

동작 순서

1. 모든 간선을 가중치 오름차순 정렬
2. 가장 싼 간선부터 순회
3. 두 정점이 서로 다른 집합이면 채택하고 두 집합을 병합
4. 같은 집합이면 사이클이 되므로 폐기
5. 채택 간선이 V-1개가 되면 종료

유니온 파인드(Disjoint Set)

"두 정점이 이미 같은 덩어리인가"를 판정하는 자료구조. 크루스칼의 사이클 판정을 담당.

• parent 배열: parent[i]는 i가 속한 집합의 부모. 초기값은 자기 자신
• find(x): x가 속한 집합의 대표(루트)를 반환
• union(a, b): 두 집합을 하나로 병합. 이미 같으면 false

최적화 두 가지

• 경로 압축(Path Compression): find 재귀 결과를 parent에 대입해 트리를 평탄화. 다음 조회부터 거의 O(1)
• 랭크 합치기(Union by Rank/Size): 작은 트리를 큰 트리 아래로 붙여 높이 증가 억제

둘을 함께 적용하면 연산당 상각 복잡도는 사실상 상수에 수렴(역아커만 함수)

시간 복잡도

정렬이 지배적. O(E log E). E는 최대 V²이므로 O(E log V)로도 표기 가능. 유니온 파인드 부분은 거의 상수

구현

class Solution {
    static int[] parent;

    public int solution(int n, int[][] costs) {
        int answer = 0;
        int edgeCnt = 0;

        Arrays.sort(costs, (a, b) -> a[2] - b[2]);

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

        for (int i = 0; i < costs.length; i++) {
            int a = costs[i][0];
            int b = costs[i][1];
            int cost = costs[i][2];

            if (union(a, b)) {
                answer += cost;
                edgeCnt++;
                if (edgeCnt == n - 1) break;
            }
        }
        return answer;
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);   // 경로 압축
    }

    static boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;             // 같은 집합, 사이클
        parent[b] = a;
        return true;
    }
}

구현 주의점

• 비교자 a[2] - b[2]는 값이 크면 오버플로 위험. Integer.compare(a[2], b[2])가 안전
• find를 재귀로 구현하면 정점 수가 매우 클 때 스택 오버플로 가능. 반복문 버전 고려
• edgeCnt가 V-1에 도달하면 조기 종료해 남은 간선 순회를 생략

3. 프림(Prim)

정점 중심 접근. 임의의 시작 정점 하나에서 출발해 현재 덩어리 밖으로 나가는 간선 중 최소를 골라 덩어리를 키움

동작 순서

1. 시작 정점을 비용 0으로 우선순위큐에 투입
2. 큐에서 최소 비용 간선을 꺼냄
3. 도착 정점이 이미 방문 상태면 폐기(사이클)
4. 미방문이면 방문 처리하고 비용 누적
5. 해당 정점의 인접 간선 중 미방문 정점행을 큐에 추가
6. 방문 정점이 V개가 되면 종료

방문 처리 시점이 핵심. offer 시점이 아니라 poll 시점에 방문 처리. offer 시점에 처리하면 나중에 더 싼 간선이 등장해도 반영되지 않음

Lazy Prim과 Eager Prim

구분	Lazy Prim	Eager Prim
방식	유효하지 않은 간선도 일단 큐에 넣고 poll 때 걸러냄	정점별 최소 비용만 갱신 관리
큐 크기	최대 E	최대 V
구현 난이도	단순, 코테에서 주로 사용	인덱스 힙 또는 key 배열 필요

시간 복잡도

이진 힙 기반 O(E log V). 인접 행렬과 배열 탐색으로 구현하면 O(V²)이며, 밀집 그래프에서는 오히려 이쪽이 유리

구현

class Solution {
    static List<Edge>[] graph;
    static boolean[] vis;
    static int n;

    public int solution(int n, int[][] costs) {
        this.n = n;
        graph = new List[n];
        vis = new boolean[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < costs.length; i++) {
            int a = costs[i][0];
            int b = costs[i][1];
            int cost = costs[i][2];
            graph[a].add(new Edge(b, cost));   // 무방향, 양쪽 등록
            graph[b].add(new Edge(a, cost));
        }

        return prim(0);                        // 시작점 무관, 총합 동일
    }

    static int prim(int start) {
        int total = 0;
        int visited = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (vis[cur.node]) continue;       // 이미 편입, 사이클
            vis[cur.node] = true;              // poll 시점 방문 처리
            visited++;
            total += cur.cost;
            if (visited == n) break;

            for (Edge next : graph[cur.node]) {
                if (!vis[next.node]) {
                    pq.offer(next);
                }
            }
        }
        return total;
    }

    static class Edge implements Comparable<Edge> {
        int node;
        int cost;

        public Edge(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}

4. 크루스칼과 프림 비교

항목	크루스칼	프림
기준	간선 중심	정점 중심
핵심 자료구조	정렬 + 유니온 파인드	인접 리스트 + 우선순위큐
중간 상태	여러 개의 분리된 숲(Forest)	항상 하나의 연결된 트리
사이클 판정	find 결과 비교	visited 배열
시간 복잡도	O(E log E)	O(E log V)
유리한 상황	희소 그래프(E가 작음)	밀집 그래프(E가 V2에 근접)
비연결 그래프	최소 신장 숲을 자연스럽게 생성	시작 정점이 속한 연결 요소만 처리

선택 기준

• 간선 목록이 그대로 주어지면 크루스칼이 자연스러움. 인접 리스트 구성 단계가 불필요
• 정점 수 대비 간선이 매우 많으면 프림이 유리
• 그래프가 여러 덩어리로 나뉠 가능성이 있으면 크루스칼

SUMMARY

• MST는 모든 정점을 연결하는 간선 V-1개의 가중치 합 최소 트리
• 크루스칼은 간선 정렬 후 사이클 없는 것만 채택, 유니온 파인드로 판정
• 프림은 한 정점에서 시작해 덩어리 밖 최소 간선으로 확장, poll 시점 방문 처리
• 두 알고리즘 모두 Cut Property가 정당성의 근거이며 총합은 동일