[프로그래머스] 코딩테스트 연습 - 77

level 3 - 섬 연결하기

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

입출력 예시
n : 4
costs : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
-> 4

function solution(n, costs) {
    var answer = 0;
    var cnt = 0;
    var parent = [...Array(n).keys()];
    costs.sort((a, b) => a[2] - b[2])
    for(var i=0; i<costs.length; i++) {
        if (union(costs[i][0], costs[i][1]) == -1) {
            answer += costs[i][2];
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    function find(num){
        if (parent[num] == num) {
            return num;
        }
        parent[num] = find(parent[num]);
        return parent[num];
    }
    function union(a, b) {
        a = find(a);
        b = find(b);

        if (a == b) {
           return a;   
        } else if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
        return -1;
    }
    return answer;
}

예전에 데이터구조 배울때 parent 사용해서 뭐 어쩌고 했는데,,, 지금 또 해보니까 기억이 새록새록 난다