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

그리디 문제입니다.

 

가중치 그래프가 주어졌을 때, 최소 신장 트리를 구하는 문제입니다.

최소 신장 트리는 가중치가 가장 작은 간선부터 선택하고, 선택된 노드들은 유니온-파인드 연산을 통해 중복되지 않게 간선을 연결하는 방법을 사용합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static int[] parents;
    public static int solution(int n, int[][] costs) {
        int answer = 0;

        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        parents = new int[n];
        for(int i=0; i<n; i++) parents[i] = i;

        for(int i=0; i<costs.length; i++){
            if(union(costs[i][0], costs[i][1])){
                answer += costs[i][2];
            }
        }

        return answer;
    }

    private static boolean union(int a, int b) {
        int root1 = find(a);
        int root2 = find(b);

        if(root1 == root2) return false;

        if(root1>root2){
            parents[root2] = root1;
        }else {
            parents[root1] = root2;
        }

        return true;
    }

    private static int find(int a) {
        if(a == parents[a]){
            return a;
        }

        return parents[a] = find(parents[a]);
    }
}