+) 그 전에 스패닝 트리란?
※ 그래프 내 모든 정점을 포함하는 부분 그래프.
최소 스패닝 트리란? (Minimum spanning tree)
- 혹은 Minimum Weight Spanning tree (최소 가중치 스패닝 트리)라고도 불림.
- 가중 + 무방향 그래프의 모든 정점을 연결하면서 사이클을 이루지 않음 + 그래프를 이루는 모든 가중치의 합이 최소인 트리를 말함.
특징
- 그래프 내 N개의 정점이 있다고 할 때, 각 스패닝 트리는 N-1개의 간선을 가진다.
- 한 그래프 내에는 여러 개의 최소 스패닝 트리가 존재할 수 있다.
- 만약 그래프 내 모든 간선의 가중치가 같다면, 모든 스패닝 트리는 항상 최소의 가중치 합을 가진다.
알고리즘
프림 알고리즘
- 주어진 그래프에서 한 정점을 선택하여 트리를 만듦.
- 그래프의 모든 간선이 들어있는 집합을 만듦.
- 모든 정점이 시작 트리에 포함될 때까지 아래의 과정을 반복함.
- 시작 트리에 포함되어있는 정점과 포함되어있지 않은 정점을 잇는 간선 중, 최소 가중치를 갖는 간선을 선택한다.
- 위에서 시작 트리에 포함되어있지 않은 정점을 시작 트리에 추가한다.
- 위에서 찾은 최소 가중치를 갖는 간선을 간선 집합에 추가한다.
크루스칼 알고리즘
- 그래프의 각 정점 하나하나가 하나의 트리가 되는 트리 집합을 만든다.
→ 즉, 정점 한 개로 이루어진 트리가 정점의 개수만큼 존재하게 된다. - 그래프의 모든 간선이 들어있는 집합을 만든다.
- 2번의 집합이 빌 때까지 아래의 과정을 반복한다.
- 2번의 집합에서 가중치가 최소인 간선을 제거한다.
- 만약 위에서 제거한 간선이 1번에서 만든 트리 집합 내 두 트리를 연결하는 것이라면, 해당 간선을 트리 집합에 추가함으로써 두 트리를 하나의 트리로 결합한다.
※ 외에도 Reverse-delete 알고리즘, 보루프카 알고리즘이 있다고 함.
문제 풀이 - 백준 1197번 최소 스패닝 트리
처음 관련 알고리즘을 알아봤을 땐 프림 알고리즘 쪽이 조금 더 이해가 쉬워서 그쪽으로 구현을 시도했었다. 보자마자 '최소 힙을 써야겠다'라는 생각이 들었고, 정점 및 간선 개수도 고려해서 최소 힙을 직접 짜서 풀이를 시도했다. 아래 코드는 제출한 코드고, 시간 초과로 (...) 실패했다.
// 시간 초과 코드
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
class PriorityQueue {
constructor () {
this.queue = [];
}
bubbleUp () {
let idx = this.queue.length - 1;
let node = this.queue[idx];
while (idx > 0) {
const parentIdx = Math.floor((idx - 1) / 2);
const parentNode = this.queue[parentIdx];
if (parentNode.weight <= node.weight) break;
this.queue[parentIdx] = node;
this.queue[idx] = parentNode;
idx = parentIdx;
}
}
bubbleDown () {
let idx = 0;
let node = this.queue[idx];
const length = this.queue.length;
while (true) {
const leftChildIdx = 2 * idx + 1;
const rightChildIdx = 2 * idx + 2;
let swap = null;
if (leftChildIdx < length) {
if (this.queue[leftChildIdx].weight < node.weight) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(swap === null && this.queue[rightChildIdx].weight < node.weight) ||
(swap !== null && this.queue[rightChildIdx].weight < this.queue[swap].weight)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.queue[idx] = this.queue[swap];
this.queue[swap] = node;
idx = swap;
}
}
enqueue (edge) {
this.queue.push(edge); // edge => { v1, v2, weight }
this.bubbleUp();
}
dequeue () {
const root = this.queue[0];
const end = this.queue[this.queue.length - 1];
if (this.queue.length > 0) {
this.queue[0] = end;
this.bubbleDown();
}
return root;
}
}
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
const [v, e] = input.shift();
const adjacencyList = {};
for (let i = 1; i <= v; i++) {
adjacencyList[i] = [];
}
for (let i = 0; i < e; i++) {
const [v1, v2, weight] = input[i];
adjacencyList[v1].push({ node: v2, weight});
adjacencyList[v2].push({ node: v1, weight});
}
let spanningTree = new Set();
let edges = [];
spanningTree.add(1);
let sum = 0;
const pq = new PriorityQueue();
for (const edge of adjacencyList[1]) {
pq.enqueue({ v1: 1, v2: edge.node, weight: edge.weight });
}
while (spanningTree.size < v) {
const minEdge = pq.dequeue();
if (spanningTree.has(minEdge.v2)) {
continue;
}
spanningTree.add(minEdge.v2);
edges.push(minEdge);
sum += minEdge.weight;
adjacencyList[minEdge.v2].forEach((e) => {
pq.enqueue({ v1: minEdge.v2, v2: e.node, weight: e.weight });
});
}
console.log(sum);
process.exit();
});- 1번 정점을 먼저 트리에 넣고, 1번 정점을 포함하는 모든 간선들을 최소 힙에 넣는 것에서 시작한다.
- 모든 정점들이 트리에 포함될 때 까지 while문을 통해 반복을 돌린다. 최소 힙에서 아직 트리에 포함되어있지 않은 정점을 잇고, 가장 작은 가중치의 간선을 뽑는 과정을 반복한다.
위 알고리즘이 시간 초과가 났기 때문에 더 빨리 실행될 수 있도록 코드를 고치거나, 다른 알고리즘을 시도해보기로 했다. 마침 스패닝 트리 문제 풀이는 처음이라, 이왕 이렇게 된 거 크루스칼 알고리즘도 구현해보기로 했다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
const [v, e] = input.shift();
let sum = 0;
const parentObj = {};
for (let i = 1; i <= v; i++) {
parentObj[i] = i; // 자기 자신을 부모로 갖는 트리 집합
}
const edges = input.sort((e1, e2) => e1[2] - e2[2]);
const findParent = (v) => {
let parent = v;
while (parentObj[parent] !== parent) {
parent = parentObj[parent];
}
return parent;
};
const union = (v1, v2) => {
const parent1 = findParent(v1);
const parent2 = findParent(v2);
return parentObj[parent2] = parent1;
};
const isConnected = (v1, v2) => {
return findParent(v1) === findParent(v2);
};
for (const edge of edges) {
const [v1, v2, weight] = edge;
if (!isConnected(v1, v2)) {
sum += weight;
union(v1, v2);
}
}
console.log(sum);
process.exit();
});
- 입력으로 받는 간선의 집합을 최초에 한 번 가중치로 정렬해준다.
- 그래프의 각 정점 하나하나가 하나의 트리가 되는 트리 집합(parentObj)를 만든다.
- 최초에는 모든 정점의 부모가 자기 자신으로 지정되어있다. 즉, 부모가 자기 자신인 정점은 곧 루트가 된다.
- 각 간선들을 돌며 아직 이어지지 않은 간선 내 두 정점을 병합하는 과정을 거친다.
- 이 때 사용하는 것이 Union-Find 알고리즘이다.
- 아직 이어지지 않은 간선을 병합할 때, 해당 간선의 가중치를 가중치 총합에 더한다.
반례나 테스트 코드는 문제 없이 풀려서 저걸로 해결이 잘 될 줄 알았는데... 또 시간 초과로 틀려서, 어찌된 일인가 하고 좀더 살펴보았다. 결론적으로, union 메서드를 아래와 같이 변경함으로써 훨씬 빠른 속도로 문제를 해결할 수 있었다.
const union = (v1, v2) => {
const parent1 = findParent(v1);
const parent2 = findParent(v2);
// 부모의 크기를 비교하여, 루트를 내림차순으로 유지시킨다
if (parent1 < parent2) return parentObj[parent2] = parent1;
else return parentObj[parent1] = parent2;
};
처음엔 이게 무슨 변화를 주나 싶었는데... 좀 찾아보니 트리의 높이에 영향을 주기 때문이라는 것을 알아냈다. 아래는 내가 빠르게 찾아보면서 아주 간략하게 이해한 이유이다.
- Union Find는 트리를 거슬러 올라가며 각 정점의 루트의 탐색을 진행한다.
- 따라서 트리의 높이가 높으면 높을 수록, 상대적으로 탐색에 더 오랜 시간이 걸리게 된다.
- 그러므로 병합하려는 각 트리의 특정 기준점을 비교함으로써, 더 작은 트리를 더 큰 트리에 합치므로써 트리의 높이가 과하게 높아지는 것을 방지한다.
→ 이와 같은 Union Find의 최적화 기법을 Union By Rank라고 한다고...
결론적으로는 Union By Rank를 통한 병합 과정의 최적화까지 추가하여 문제를 통과할 수 있었다.
- 처음엔 프림 알고리즘이 다익스트라도 생각나서 좀더 이해가 쉬웠는데... 크루스칼도 구현해보니 한층 와닿게 이해가 되는 것 같다.
- 무엇보다 우선순위 큐를 구현할 필요가 없어서, 덜 귀찮고 좋았다ㅎㅎ
'공부 > 알고리즘' 카테고리의 다른 글
| 외판원 순환 문제 알아보기 (3) | 2024.11.10 |
|---|---|
| 위상 정렬 알아보기 (0) | 2024.08.31 |
| Monotonic Stack에 대하여 (0) | 2024.04.14 |
| 다익스트라 알고리즘 정리 (1) | 2023.12.28 |
| 이진 힙(Binary Heap) 정리 (0) | 2023.12.19 |
