출처 : https://programmers.co.kr/learn/courses/30/lessons/42861
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.
n costs return
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
가중치가 적은 간선부터 채택하는 크루스칼 알고리즘으로 풀었다.
costs를 비용이 적은 순으로 정렬하고,
가장 적은 값부터 보면서 모든 정점이 하나의 부모를 가지면서 선택된 간선이 n-1개가 될 때까지 while문을 돌렸다.
function solution(n, costs) {
function union(a, b) {
let rootA = find(a);
let rootB = find(b);
if (rootA === rootB) return false;
parent[rootB] = rootA;
return true;
}
function find(a) {
if (parent[a] === a) return a;
return (parent[a] = find(parent[a]));
}
costs.sort(function (a, b) {
return a[2] - b[2];
});
let answer = 0,
parent = [],
count = 0;
for (let i = 0; i < n; i++) parent.push(i);
while (count < n - 1) {
const min = costs.shift();
if (find(min[0]) != find(min[1])) {
union(min[0], min[1]);
answer += min[2];
count++;
}
}
return answer;
}