프로그래머스 섬 연결하기 (JAVA)

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

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

 

저는 해당 문제를 크루스칼을 통해서 문제를 해결하였습니다.

크루스칼을 통해 MST를 구성하면서 가장 작은 가중치의 합을 구하였습니다.

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = kruskal(n,costs);
        return answer;
    }
    
    private int findSet(int now, int[] parent){
        if(now == parent[now]){
            return now;
        }    
        return parent[now] = findSet(parent[now], parent);
    }
    private boolean unionSet(int a,int b,int[] parent){
        int aParent = findSet(a, parent);
        int bParent = findSet(b, parent);
        if(aParent == bParent){
            return false;
        }
        parent[aParent] = bParent;
        return true;
    }
    private int kruskal(int n, int[][] costs){
        int[] parent = new int[n];
        for(int i = 0 ; i < n ; i++){
            parent[i] = i;
        }
        Arrays.sort(costs,(o1,o2)->{
            return o1[2] - o2[2];
        });
        int result = 0;
        for(int[] edge : costs){
            if(unionSet(edge[0],edge[1],parent)){
                result += edge[2];
            }
        }
        return result;
    }
}