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

https://programmers.co.kr/learn/courses/30/lessons/42861?language=java

문제 해석

노드들간의 연결과 가중치가 주어진다

모든 섬을 연결하면서 가장 작은 비용이 드는 경우의 비용을 구하는 문제

문제 풀이

노드 수 100개로 탐욕적 방법으로 서치가 가능한 문제이다

Kruskal 이라고 가장 작은 비용이 드는 간선을 하나씩 선택하면서 사이클이 생성되는지만 체크하는 알고리즘을 사용했다. 이 알고리즘은 사이클인지 판단하는 Union-Find가 핵심

Find - 현재 연결된 최고 조상을 찾는다

Union - 두 노드를 결합해 최고 조상을 같게 만든다

결국 Union으로 나온 결과가 false라는건 두 노드의 최고 조상이 같다는 뜻이기 때문에 두 노드를 연결하면 사이클이 생성된다!! 두 노드의 최고 조상이 다른경우 Union에서 두 노드를 연결시킨다.

import java.util.*;
class CustomComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] cost1, int[] cost2) {
        if (cost1[2] > cost2[2]) {
            return 1;
        } else if (cost1[2] == cost2[2]) {
            return 0;
        } else {
            return -1;
        }
    }
}

class Solution {
    int[] Parent;
    int[][] map;

    public int solution(int n, int[][] costs) {
        int answer = 0;

        map = new int[n][n];
        Parent = new int[n];

        for (int i = 0; i < n; i++) {
            Parent[i] = i;
        }
        Arrays.sort(costs, new CustomComparator());


        for(int i = 0; i < costs.length; i++){
            //System.out.println(costs[i][0]);
            if(Union(costs[i][0], costs[i][1])){
                //System.out.println(i);
                answer += costs[i][2];
            }
        }

        return answer;
    }

    public int Find(int n) {
        if (n == Parent[n]) return n;
        else return Parent[n] = Find(Parent[n]);
    }

    public boolean Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if (a == b) return false;
        else {
            if (a > b) Parent[a] = b;
            else Parent[b] = a;
        }
        return true;
    }

}