Level 3 210925 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
입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
My solution
크루스칼 알고리즘, 최소신장 문제
테스트케이스를 돌려보니 이미 하나 이상의 간선이 연결된 섬들이면서 서로 연결되어 있지 않아 거쳐서 이동할 수 없는 케이스가 있었다. 그래서 이미 간선이 연결된 섬에 대한 체크로는 이것을 해결할 수 없다고 생각했다.
최소 비용의 간선으로 계속해서 이어가면서 거쳐서라도 갈 수 있는 섬이라면 해당 간선은 건너뛰게 하는 조건이 필요했다. 이것은 최소 신장(스패닝) 트리를 찾기 위한 크루스칼 알고리즘과 같다.
분리된 섬을 연결할 지에 대해서 판단하기 위해서는 사이클이 생기지 않게 추가해야 모든 분리된 섬들이 최소비용과 최소 개수의 간선으로 연결된 최소신장트리를 만든다는 것을 알 수 있었고 이는 크루스칼 알고리즘의 목표였다.
이 알고리즘의 동작방식은 간선의 가중치를 오름차순으로 정렬하고 간선 배열(리스트)에서 사이클을 형성하지 않은 간선을 선택하여 가장 낮은 가중치를 먼저 선택하여 최소 신장 트리에 추가하는 것이다.
Union-Find를 이용해 사이클이 발생하는지 하지 않는지 조사하면서 사이클이 발생하지 않을때만 연결시켜준다.
(Union-Find : 집합을 관리하는 자료구조 , 상호 배타적 집합(disjoint set))
find 함수는 미리 정의해둔 parent 배열을 통해 자신의 부모노드를 재귀적으로 찾아낸다.
function find(n) {
// 부모가 자기 자신인 경우
if (parent[n] === n) {
return n;
} else {
// 재귀함수를 이용하여 부모를 추적
return (parent[n] = find(parent[n]));
}
}union은 둘의 부모 노드가 다를 때 연결한다.
function union(n1, n2) {
// n1과 n2를 합치기 전에 부모부터 찾아야 한다.
n1 = find(n1);
n2 = find(n2);
// 대게, 부모를 합칠때는 일반적으로 더 작은 값쪽을 합친다.
if (n1 !== n2) {
// n2 > n1
// 부모가 다르다면 n2의 부모를 n1으로 설정
if (n2 > n1) {
parent[n2] = n1;
} else {
parent[n1] = n2;
}
}
}서로소 집합이기 때문에 parent 배열에 있는 부모노드가 서로 다르다면 union해도 된다.
costs.forEach((cost) => {
// 부모노드가 다르면 사이클 생성 안됨 >> 연결 O
if (find(cost[0]) !== find(cost[1])) {
union(cost[0], cost[1]);
minCost += cost[2];
}
});소스 코드
function solution(n, costs) {
let answer = 0;
const parent = Array(n)
.fill()
.map((_, i) => i); // 부모노드는 자기자신으로 초기화
let minCost = 0;
costs.sort((a, b) => a[2] - b[2]);
function find(n) {
// 부모가 자기 자신인 경우
if (parent[n] === n) {
return n;
} else {
// 재귀함수를 이용하여 부모를 추적
return (parent[n] = find(parent[n]));
}
}
function union(n1, n2) {
// n1과 n2를 합치기 전에 부모부터 찾아야 한다.
n1 = find(n1);
n2 = find(n2);
// 대게, 부모를 합칠때는 일반적으로 더 작은 값쪽을 합친다.
if (n1 !== n2) {
// n2 > n1
// 부모가 다르다면 n2의 부모를 n1으로 설정
if (n2 > n1) {
parent[n2] = n1;
} else {
parent[n1] = n2;
}
}
}
costs.forEach((cost) => {
// 부모노드가 다르면 사이클 생성 안됨 >> 연결 O
if (find(cost[0]) !== find(cost[1])) {
union(cost[0], cost[1]);
minCost += cost[2];
}
});
return (answer = minCost);
}
test("solution", () => {
expect(
solution(4, [
[0, 1, 1],
[0, 2, 2],
[1, 2, 5],
[1, 3, 1],
[2, 3, 8],
])
).toBe(4);
expect(
solution(5, [
[0, 1, 5],
[1, 2, 3],
[2, 3, 3],
[3, 1, 2],
[3, 0, 4],
[2, 4, 6],
[4, 0, 7],
])
).toBe(15);
expect(
solution(5, [
[0, 1, 1],
[3, 4, 1],
[1, 2, 2],
[2, 3, 4],
])
).toBe(8);
expect(
solution(4, [
[0, 1, 5],
[1, 2, 3],
[2, 3, 3],
[1, 3, 2],
[0, 3, 4],
])
).toBe(9);
expect(
solution(5, [
[0, 1, 1],
[3, 1, 1],
[0, 2, 2],
[0, 3, 2],
[0, 4, 100],
])
).toBe(104);
expect(
solution(6, [
[1, 4, 1],
[0, 3, 2],
[1, 2, 2],
[0, 4, 3],
[2, 5, 3],
[4, 5, 4],
[0, 1, 5],
[3, 4, 10],
])
).toBe(11);
expect(
solution(5, [
[0, 1, 1],
[2, 3, 1],
[3, 4, 2],
[1, 2, 2],
[0, 4, 100],
])
).toBe(6);
expect(
solution(5, [
[0, 1, 1],
[0, 4, 5],
[2, 4, 1],
[2, 3, 1],
[3, 4, 1],
])
).toBe(8);
expect(
solution(5, [
[0, 1, 1],
[0, 2, 2],
[0, 3, 3],
[0, 4, 4],
[1, 3, 1],
])
).toBe(8);
});