99클럽 코테 스터디 16일차 TIL: [프로그래머스] 섬 연결하기

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

프로그래머스

 

유니온 파인드(+ 그리디)를 사용하면 아주 간단하게 풀 수 있는 문제이다. (그런데 나는 유니온 파인드를 머릿 속에서 잊고 있어서 못 풀었다.)

• 유니온 파인드를 통해 모든 노드가 하나의 집합이 되도록 다리를 건설하면 된다.
• 그런데 최소 비용이 되도록 다리를 건설해야 하므로, 건설 비용이 적은 다리부터 건설하면 된다.
• 즉, "다리 건설 비용이 적은 순"으로, "모든 노드가 하나의 집합이 될 때까지" 다리를 건설하면 된다.

import java.util.*;

class Solution {
    
    int[] parents;
    
    public int solution(int n, int[][] costs) {
        parents = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        
        // 비용이 적은 순으로 정렬
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        
        // 비용이 적은 순으로, 모든 노드가 하나의 집합에 속할 때까지 다리 건설
        int answer = 0;
        for (int[] cost : costs) {
            // 다른 집합인 경우에만 합치기 (같은 집합인 경우엔 합칠 필요 없음)
            if (getParents(cost[0]) != getParents(cost[1])) {
                union(cost[0], cost[1]);
                answer += cost[2];
            }
        }
        
        return answer;
    }
    
    public int getParents(int n) {
        if (parents[n] == n) return n;
        return getParents(parents[n]);
    }
    
    public void union(int n1, int n2) {
        int p1 = getParents(n1);
        int p2 = getParents(n2);
        if (p1 < p2) {
            parents[p2] = p1;
        } else {
            parents[p1] = p2;
        }
    }
}