섬 연결하기

import java.util.*;
 
class Solution {
    private static int[] parent;
    
    // 부모 설정
    public static void Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if (a > b) {
            parent[a] = b;
        } else {
            parent[b] = a;
        }
    }
    // 부모 찾기
    public static int Find(int x) {
        if (parent[x] == x)
            return x;
        else
            return Find(parent[x]);
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        //부모 초기화
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
        // 비용 오름차순 정렬
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[2] - o2[2];
            }
        });
 
        for(int i=0;i<costs.length;i++){
            int a = costs[i][0];
            int b = costs[i][1];
            // 사이클이 생기지 않을 경우
            if(Find(a) != Find(b)){
                Union(a, b);
                answer += costs[i][2];
            }
        }
        return answer;
    }
}

크루스칼 알고리즘을 통해 최소 신장 트리(MST)를 구하여 해결하였다.

 

참고 사이트 : https://sskl660.tistory.com/72