[프로그래머스] 섬 연결하기

프로그래머스 <섬 연결하기>

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

코딩테스트 연습 - 섬 연결하기

---

<섬 연결하기>

n개의 섬을 모두 연결하는 다리를 건설하는 총 비용의 최솟값을 구하여라.

---

문제 해결

kruskal 알고리즘을 사용하여 해결하였다.

 

kruskal 알고리즘

- 최소 신장 트리 알고리즘

- edge의 weight가 작은 순으로 정렬하여 선택한다.

- union find 알고리즘을 사용한다.

 

1) 모든 노드를 독립적인 집한으로 만든다.

2) 모든 edge를 cost 기준으로 정렬하고 작은 순서대로 두 노드를 비교한다.

3) 두 노드의 root를 확인하고 서로 다를 경우 두 노드를 연결한다.

 

union find 알고리즘

- Disjoint Set을 표현할 때 사용하는 알고리즘

- find : 노드의 root를 구한다.

- union : 두 노드를 합친다.

- path compression : find를 실행한 노드에서 거쳐간 노드를 루트에 연결

- union by rank : tree의 depth를 보고 rank가 큰 노드에 작은 노드를 연결

---

코드

import java.util.PriorityQueue;
class Solution {
    static int[] root;
    static int[] rank;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        root = new int[n];
        rank = new int[n];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        for(int i = 0 ; i < n; i++){
            root[i] = i;
            rank[i] = 1;
        }
        int len = costs.length;
        for(int i = 0 ; i < len; i++){
            int a = costs[i][0];
            int b = costs[i][1];
            int c = costs[i][2];
            pq.add(new Node(a,b,c));
        }
        
        while(!pq.isEmpty()){
            Node pop = pq.poll();
            int popA = pop.a;
            int popB = pop.b;
            int popCost = pop.cost;
            
            if(union(popA, popB)){
                answer += popCost;
            }
            
            if(check(n)){
                break;
            }
            
        }
        
        return answer;
    }
    public static boolean check(int n){
        int value = root[0];
        for(int i = 1; i < n; i++){
            if(value != root[i]){
                return false;
            }
        }
        return true;
    }
    public static int find(int n){
        if(root[n] == n){
            return n;
        }
        return root[n] = find(root[n]);
    }
    
    public static boolean union(int a, int b){
        int rA = find(a);
        int rB = find(b);
        if(rA == rB){
            return false;
        }
        
        if(rank[rA] > rank[rB]){
            root[rB] = rA;
        }else{
            root[rA] = rB;
            if(rank[rA] == rank[rB]){
                rank[rA]++;
            }
        }
        return true;
        
    }
}
class Node implements Comparable<Node>{
    int a, b, cost;
    public Node(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.cost = c;
    }
    
    public int compareTo(Node other){
        if(this.cost > other.cost){
            return 1;
        }else if(this.cost == other.cost){
            return 0;
        }else{
            return -1;
        }
    }
}

---

결과

---