설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
제한 사항
입출력 예
numbers | cost | return |
---|---|---|
4 | [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] | 4 |
입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
전형적인 MST문제입니다.
저는 크루스칼 알고리즘을 사용해서 문제를 해결해보겠습니다.
function solution(n, costs) {
// 크루스칼 알고리즘 구현에 필요한 유니온 파인드 함수들과 변수 선언
const set = [...Array(n)].map((_, i) => i);
const find = a => set[a] = a == set[a] ? a : find(set[a]);
const union = (a, b) => {
a = find(a);
b = find(b);
a > b ? set[a] = b : set[b] = a;
};
const is_same_parent = (a, b) => find(a) == find(b);
return (
costs
.sort((a, b) => a[2] - b[2])
.reduce((m, [a, b, cost]) => {
// a와 b가 연결됐다면 넘어가기
if (is_same_parent(a, b)) return m;
// a, b를 연결
union(a, b);
// 비용 누적
m += cost;
return m;
}, 0)
);
}