문제
풀이
요구사항
최소신장트리를 만들어라.
해결방안
최소신장트리 문제는 크루스칼 알고리즘을 사용해서 풀 수 있다.
매번 느끼는 거지만 크루스칼 알고리즘 문제는 구현은 어렵지 않지만 문제를 보고 최소신장트리를 떠올리기까지가 어려운 것 같다.
처음엔 우선순위 큐와 BFS를 응용해서 풀려고 해봤다.
Priority Queue + BFS
1번 도시부터 인접한 노드의 간선 정보를 우선순위 큐에 넣는다. 그럼 비용이 작은 간선부터 dequeue 할 수 있다. 또한 이미 정복한 도시는 visited를 true로 바꾸어 다시 접근하지 못하도록 한다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, t] = input[0].split(' ').map(Number);
const graph = Array.from({ length: N + 1 }, () => []);
const edges = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const visited = Array(N + 1).fill(false);
for (const [A, B, C] of edges) {
graph[A].push([B, C]);
graph[B].push([A, C]);
}
// i번 노드를 탐색할 때, i번 노드와 연결된 다른 노드들을 우선순위 큐에 저장
// bfs실행
// 정복한 곳에서 인접한 노드로 이동
class PriorityQueue {
constructor() {
this.heap = [];
}
enqueue(node, priority) {
this.heap.push({ node, priority });
this.heapifyUp(this.heap.length - 1);
}
heapifyUp(idx) {
while (idx > 0) {
const pIdx = (idx - 1) >> 1;
if (this.heap[pIdx].priority > this.heap[idx].priority) {
[this.heap[pIdx], this.heap[idx]] = [this.heap[idx], this.heap[pIdx]];
} else break;
idx = pIdx;
}
}
dequeue() {
const min = this.heap[0];
const temp = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = temp;
this.heapifyDown(0);
}
return min;
}
heapifyDown(idx) {
while (idx < this.heap.length - 1) {
const lcIdx = idx << (1 + 1);
const rcIdx = idx << (1 + 2);
let smaller = idx;
if (this.heap[lcIdx] && this.heap[lcIdx].priority < this.heap[smaller].priority) smaller = lcIdx;
if (this.heap[rcIdx] && this.heap[rcIdx].priority < this.heap[smaller].priority) smaller = rcIdx;
if (idx === smaller) break;
[this.heap[idx], this.heap[smaller]] = [this.heap[smaller], this.heap[idx]];
idx = smaller;
}
}
size() {
return this.heap.length;
}
}
let answer = 0;
function bfs() {
const pq = new PriorityQueue();
pq.enqueue(1, 0);
let count = 0;
while (pq.size() > 0) {
const { node, priority } = pq.dequeue();
if (!visited[node]) {
if (node !== 1) {
answer += priority + count++ * t;
}
visited[node] = true;
for (const [n, p] of graph[node]) {
// 이미 정복한 도시는 큐에 삽입하지 않는다.
if (!visited[n]) {
pq.enqueue(n, p);
}
}
}
}
}
bfs();
console.log(answer);문제에 있는 예시 뿐만 아니라 다른 예시들도 여러개 시도해보았는데 다 올바른 정답이 나왔다.
하지만 제출을 하면 2%에서 틀렸습니다가 나와서 반례를 열심히 찾아보려고 했지만 아직 못 찾았다...
MST (크루스칼)
결국 문제의 유형을 보고 풀었다.
크루스칼을 이용해서 풀면서 깨달은 점이 있는데, 굳이 1번부터 출발할 필요가 없다는 것이다.
문제에서 처음 점거하고 있는 도시가 1번 도시라는 것에 매몰되었던 것 같다. 모든 도시가 도로로 연결되어 있고 모든 도시를 점거해야하기 때문에 1번 부터 출발하지 않더라도 1번 도시를 점거하게 된다.
또한 최소비용만 구하면 되기 때문에 도시를 방문하는 순서도 중요하지 않다. 모든 비용의 합만 구하면 되기 때문이다.
코드의 구현 방식은 일반적인 크루스칼 알고리즘과 동일하지만 도시를 하나 정복할 때마다 비용이 t씩 증가하기 때문에 이 점만 유의해서 구현해주면 된다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, t] = input[0].split(' ').map(Number);
const edges = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const parent = [];
for (let i = 1; i <= N; i++) {
parent[i] = i;
}
// 간선의 비용 기준으로 오름차순 정렬
edges.sort((a, b) => a[2] - b[2]);
function union(a, b) {
if (a < b) parent[b] = a;
else parent[a] = b;
}
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
let count = 0;
let answer = 0;
for (let [a, b, c] of edges) {
a = find(a);
b = find(b);
if (a !== b) {
union(a, b);
answer += c + t * count++;
}
}
console.log(answer);
크루스칼로 문제를 풀고나서 첫 번째 코드와 어떤 동작의 차이가 있을까 생각해보았다.
두 코드는 아래와 같은 차이가 있다.
우선 크루스칼은 처음에 간선의 비용을 기준으로 모든 간선이 정렬된 다음에 시작한다.
반면에 우선순위 큐를 이용한 방식에서는 여태까지 정복한 노드에 연결되어 있던 간선들만 정렬이 진행된다는 차이점이 있었다.
이를 근거로 반례를 찾아보자.
반례
6 7 3
1 2 1
1 3 2
2 4 2
2 5 2
3 5 1
4 6 1
5 6 10
correct: 37
wrong: 45반례를 찾았다.
두 코드가 위 예시를 실행할 때 어떤 순서로 동작하는지도 비교해보자.
크루스칼 알고리즘을 사용했을 때
1 -> 2: 1 + 3 * 0 = 1
3 -> 5: 1 + 3 * 1 = 4
4 -> 6: 1 + 3 * 2 = 7
1 -> 3: 2 + 3 * 3 = 11
2 -> 4: 2 + 3 * 4 = 14
answer: 37우선순위 큐를 사용했을 때
1 -> 2: 1 + 3 * 0 = 1
2 -> 3: 2 + 3 * 1 = 5
3 -> 5: 1 + 3 * 2 = 7
5 -> 6: 10 + 3 * 3 = 19
6 -> 4: 1 + 3 * 4 = 13
answer: 45크루스칼 알고리즘을 사용했을 때는 순서에 상관없이 비용이 작은 간선부터 연결시킨다. 하지만 우선순위 큐를 사용하면 순서에 제약을 받기 때문에 더 작은 비용의 간선이 존재함에도 불구하고 정복된 도시에 인접한 도시로만 이동할 수 있기 때문에 다른 결과가 나온다.
