프로그래머스 - 섬 연결하기 (Java, 최소 신장 트리(MST), 크루스칼)

아이디어

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

크루스칼 알고리즘

 

최소 신장 트리의 경우 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

크루스칼 알고리즘 (Kruskal Algorithm) : 간선 수가 적은 경우(희소 그래프, Sparse Graph)에 적합.

프림 알고리즘 (Prim Algorithm) : 간선 수가 많은 경우(밀집 그래프, Dense Graph)에 적합.

 

크루스칼 알고리즘으로 문제를 풀었다.

 

크루스칼 알고리즘

1. 간선 가중치 기준 오름차순 정렬
2. 가중치 작은 간선부터 사이클을 만들지 않는 간선 선택 (= 그리디)
3. 간선을 최소 신장 트리 집합에 추가 (트리 간 병합)

사이클이 발생하는 경우

= 특정 간선에 대한 양쪽 노드가 이미 같은 트리에 포함되어 있는 경우
= 즉, 그래프의 루트 노드가 같은 경우

 

 

유니온 파인드(Union Find)

사이클 판별을 위해서 사용된다.

Union : 트리 간 병합

Find : 현재 노드가 속한 트리의 루트 노드 찾기. Union 내부에서 사용된다.

1. 유니온 함수를 호출하여 현재 간선에 대한 병합을 시도한다.
2. 유니온 함수 내부에서 두 노드 u, v 각각이 속한 트리의 루트 노드를 찾는다. (초기값은 자기 자신이다.)
3. 만약 루트 노드가 서로 같다면 사이클이 발생하므로 무시한다.
4. 루트 노드가 서로 다르다면 병합한다. (v의 부모 노드를 u로 설정)
5. 연결된 간선 수가 노드 수 - 1개라면 종료한다.

 

 

최적화 전략

최적화를 위해서 Path Compression과 Union by Rank 사용.

=> 루트 노드를 찾을 때 트리의 depth를 줄임으로써 시간 복잡도를 줄임

=> find()에서 루트 노드를 찾기 위해서 재귀적 호출을 하게 된다. flat 할수록, 호출 수가 줄어든다.

 

Path Compression

특정 노드가 속한 트리의 루트 노드를 반환하기 전에 부모 노드 값을 루트 노드로 업데이트 한다.

이를 통해 depth를 줄여 flat한 트리를 만듦으로써 빠르게 루트 노드를 반환할 수 있다.

 

Union by Rank

두 트리 간 병합 시 더 큰 트리로 작은 트리를 병합하는 방식이다.

rank는 트리의 depth와 비슷한 역할을 하지만 depth 값과 완전히 같지는 않다. 트리의 크기에 대한 점수라고 보면 된다.

import java.util.*;

class Solution {
    int answer = 0, cnt = 0;
    int[] p = null;
    int[] rk = null;

    public int solution(int n, int[][] costs) {
        p = new int[n];
        rk = new int[n];

        // p : 특정 노드가 속한 그래프의 루트 노드
        // rk : 특정 노드가 속한 그래프의 랭크(크기)
        for(int i = 0; i < n; i++) {
            p[i] = i;
            rk[i] = 1;
        }

        List<Edge> edges = new ArrayList<>();

        for(int i = 0; i < costs.length; i++)
            edges.add(new Edge(costs[i][2], costs[i][0], costs[i][1]));

        Collections.sort(edges);

        for(Edge e : edges){
            union(e);
            if(cnt == n - 1) break;
        }

        return answer;
    }

    int find(int x){
        if(p[x] == x) return x;
        return p[x] = find(p[x]); // Path Compression
    }

    void union(Edge e){
        int up = find(e.u);
        int vp = find(e.v);

        if(up == vp) return;

        // Union By Rank
        if(rk[up] < rk[vp]) {
            int tmp = up;
            up = vp;
            vp = tmp;
        }

        p[vp] = up;

        if(rk[up] == rk[vp]) rk[up]++;

        // 가중치 합
        answer += e.w;
        // 연결된 노드 수 증가
        cnt++;
    }
}

class Edge implements Comparable<Edge> {
    public int w;
    public int u;
    public int v;

    public Edge(int w, int u, int v){
        this.w = w;
        this.u = u;
        this.v = v;
    }

    public int compareTo(Edge e) {
        return this.w - e.w;
    }
}