[프로그래머스 알고리즘 고득점 Kit][그리디][Java] 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

크루스칼 알고리즘을 사용해 최소 신장 트리를 만든다.

1. 모든 다리를 비용 기준으로 오름차순 정렬한다.
2. 비용이 작은 다리부터 확인한다.
3. 두 섬의 대표가 다르면 사이클이 발생하지 않으므로 연결한다.
4. 해당 다리의 비용을 minCost에 더하고 두 집합을 합친다.

Union-Find

• find(): 섬이 속한 집합의 대표를 찾고 경로를 압축한다.
• union(): 서로 다른 두 집합을 하나로 합친다.
• p[x] < 0이면 x가 해당 집합의 대표이다.

시간복잡도

• 다리 정렬: O(E log E)
• Union-Find: 약 O(E)
• 전체: O(E log E)

import java.util.*;

class Solution {
    
    int N; //섬의 개수
    int[] p;
    ArrayList<Bridge> bridges;
    class Bridge {
        int u;
        int v;
        int c;
        Bridge(int u, int v, int c) {
            this.u = u;
            this.v = v;
            this.c = c;
        }
    }
    
    public int solution(int n, int[][] costs) {
        N = n;
        p = new int[N+1];
        Arrays.fill(p, -1);
        bridges = new ArrayList<>();
        
        for(int i=0; i<costs.length; i++) {
            int u = costs[i][0];
            int v = costs[i][1];
            int c = costs[i][2];
            
            bridges.add(new Bridge(u, v, c));
        }
        
        bridges.sort((b1, b2) -> {
            return Integer.compare(b1.c, b2.c);
        });
        
        int minCost = 0;
        for(Bridge bridge: bridges) {
            int u = bridge.u;
            int v = bridge.v;
            int c = bridge.c;
            
            if(find(u) != find(v)) {
                minCost += c;
                union(u, v);
            }
        }
        
        return minCost;
    }
    
    public int find(int x) {
        if(p[x] < 0) return x;
        
        return p[x] = find(p[x]);
    }
    
    public void union(int x, int y) {
        int u = find(x);
        int v = find(y);
        
        if(u == v) return;
        
        if(p[u] > p[v]) {
            int t = u;
            u = v;
            v = t;
        }
        if(p[u] == p[v]) p[u]--;
        
        p[v] = u;
    }
}