[프로그래머스] 섬 연결하기

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

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

 

그리디 알고리즘으로 레벨3 문제인데, 알고리즘을 알고 있다면 쉬운 문제일수 있지만 알고리즘을 모르는 경우에는 굉장히 어려운 문제라고 생각된다. 위 문제는 크루스칼 알고리즘을 통해서 해결해야 되고, MST 에 대해서 알고 있으면 해결 가능하다

 

MST(최소 신장 트리) : 간선의 수가 가장 적고, 총 간선의 크기가 가장 적은 그래프

참고 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

Edge 그래프들을 간선의 크기 순으로 오름차순 정렬 수행하고, 각 점에 대해 parent 를 자기 자신의 점으로 설정한 다음 union-find 전략을 사용해서 간선들을 돌면서, parent 가 다른 경우에 대해서는 간선의 크기를 더하면서 모든 점들을 돌면서 Edge 크기 총합의 최소값을 구할 수 있다. (parent 가 다른 경우, parent 업데이트를 진행해야 된다)

 

예제 코드는 아래와 같습니다.

 

import java.util.*;
class Solution {
    public static int solution(int n, int[][] costs) {
        int answer = 0;
        // kruskal algorihtm (MST)
        // Edge sort
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[2] == o2[2]) Integer.compare(o1[0],o2[0]);
                return Integer.compare(o1[2],o2[2]);
            }
        });

        int[] parent = new int[n];
        int ans = 0;
        // setup parent
        for (int i = 0; i < n; i++)
            parent[i] = i;
        for (int i = 0; i < costs.length; i++) {
            int parentFirst = find(parent, costs[i][0]);
            int parentSecond = find(parent, costs[i][1]);
            if (parentFirst != parentSecond) {
                ans += costs[i][2];
                if (parentFirst > parentSecond) parent[parentFirst] = parentSecond;
                else parent[parentSecond] = parentFirst;

            }
        }
        return ans;
    }

    public static int find(int[] parent, int x) {
        if (parent[x] == x)
            return x;
        return find(parent, parent[x]);
    }
}