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

문제 URL

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

이 문제는 최소신장트리, 크루스칼, union-find알고리즘을 사용하는 문제이다.

따라서 잘 정리된 아래 사이트에서 참고하면서 문제를 풀었다.

1) 최소신장트리 https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html 2) 크루스칼 알고리즘 https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html 3) union-find 알고리즘 https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

• 최소신장트리를 구해야한다.
  1. 간선을 가중치를 기준으로 정렬한다.
  2. 가장 가중치가 낮은 간선부터 선택한다.
  3. 이때 같은 부분집합에 속해있는 정점들에 대한 간선은 사용하면 안된다. -> union-find 알고리즘을 사용해서 같은 집합에 속했는지 확인한다.

나의 풀이

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public static int[] parent;
    public static int solution(int n, int[][] costs) {
        parent = new int[n];

        for(int i=0; i<n; i++){
            parent[i] = i;
        }

        Arrays.sort(costs, Comparator.comparingInt(a -> a[2]));

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

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

        return parent[x] = find(parent[x]);
    }

    public static void union(int x, int y){
        x = find(x);
        y = find(y);
        parent[y] = x;
    }

}