모든 섬사이의 다리를 만들고 비용 최소를 구하자 , kruskal union find

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

프로그래머스

 

특이 조건 

 

- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.

- 연결할 수 없는 섬은 주어지지 않습니다

 

조건을 기반으로 모든 섬은 연결이 가능하다라는 것을 이야기 하는 듯 하다.

 

 

문제를 해석했을때 아는 것을 사용할려고 다익스트라 알고리즘을 떠올렸지만,

 

사이클을 형성 하게 되면 최소 비용으로 모든 노드를 연결하지 못한다라는것을 알게 되었다.

 

-> MST 의 크루스칼 알고리즘은 가장 작은 간선을 선택을 하며 이때 순환이 안되는지를 확인을 계속 해준다.

: 간선을 기준으로 트리를 만드는 알고리즘이다.

 

그럼 순환이 안되는지는 어떻게 판단을 하나?

-> Union - find 알고리즘 

 

두 노드를 연결시 같은 그래프에 속하는 노드라면 , 사이클이 발생이 된다.

 

우리는 집합의 대표자(부모)를 지정하여 , 모든 노드가 대표자를 향하게 하는 깊이 1  그래프를 유지하여 , 검색의 속도를 높인다.

 

 

문제 후기 :  특정 알고리즘을 알면 상당하게 쉽게 풀리게 되는 문제이며 , 알고리즘의 위대함을 느낀 문제이다.

 

 

 

import java.util.*;

class Solution {
    int[] parent;

    // Union-Find 알고리즘
    public int findParent(int node) {
        if (parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }

    public boolean union(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a != b) {
            parent[b] = a;
            return true;
        }
        return false;
    }

    public int solution(int n, int[][] costs) { 
        parent = new int[n];
        for(int i = 0 ; i < n ; i++) {
            parent[i] = i ;
        }
        Arrays.sort(costs, Comparator.comparingInt( o -> o[2])) ; // sort by cost  
        
        int answer = 0 ;
        for(int[] item : costs) {
            // 최소 비용을 기준 즉 간선을 기준으로 선택을 하는  크루스칼 알고리즘
         if( union(item[0],item[1]) ) { //서롤 집합이 아니면, 연결을 한다. 
             answer += item[2] ;   // 집합이 아닌걸 더함 
            }
        }
        return answer ; 
    }
    
}