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 사용해서 뭐 어쩌고 했는데,,, 지금 또 해보니까 기억이 새록새록 난다