탐욕법 - 섬 연결하기

프로그래머스(탐욕법) - 섬 연결하기

해당 문제를 봤을때 제한사항으로 costs의 길이가 있기에, 한 좌표에서 각 좌표까지의 path costs를 구해 각 좌표별 최소 path를 구한 후 set에 다리를 연결 하는 방식으로 진행하려고 했습니다. 정상적으로 풀지 못해, 결국 인터넷 검색의 힘을 구했고, 해당 문제가 최소신장트리(MST), Kruskal(크루스칼) 알고리즘 과 관련된 문제라는 것을 알 수 있었습니다.

public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < costs.length; i++) {
            priorityQueue.add(costs[i]);
        }

        while (!priorityQueue.isEmpty()) {
            int[] info = priorityQueue.poll();
            if (findParent(info[0], parent) != findParent(info[1], parent)) {
                parent = union(info, parent);
                answer += info[2];
            }
        }
        return answer;
    }

    public int[] union(int[] info, int[] parent) {
        int startParent = findParent(info[0], parent);
        int endParent = findParent(info[1], parent);
        if (startParent < endParent) {
            parent[endParent] = startParent;
        } else {
            parent[startParent] = endParent;
        }
        return parent;
    }

    public int findParent(int position, int[] parent) {
        if (parent[position] == position) {
            return position;
        }

        return findParent(parent[position], parent);
    }