문제 설명
주어진 무방향 그래프가 있습니다. 그래프는 노드와 간선으로 구성되어 있으며,
각 간선은 가중치를 가지고 있습니다. 시작 노드로부터 다른 모든 노드까지의 최단 경로를
구하는 문제를 풀어보겠습니다. 이 알고리즘은 다익스트라 알고리즘을
이용하여 해결할 수 있습니다.
문제 정의
아래의 그래프를 가정해 보겠습니다. 노드의 개수는 n, 간선의 개수는 e입니다.
입력
n = 6
e = 9
edges = [
[1, 2, 1],
[1, 3, 4],
[2, 3, 2],
[2, 4, 5],
[3, 4, 1],
[4, 5, 3],
[3, 5, 6],
[5, 6, 2],
[4, 6, 1]
]
start = 1
주어진 그래프에서 start 노드(1번 노드)로부터 다른 노드까지의 최단 경로를
구하는 함수를 작성하세요. 함수는 각 노드까지의 최소 거리를 배열로 반환해야 합니다.
알고리즘 개요
다익스트라 알고리즘은 그래프 이론에서 주어진 노드로부터 다른 모든 노드까지의
최단 경로를 구하는 데 사용됩니다. 이 알고리즘은 우선순위 큐를 활용하여
가장 짧은 경로를 찾는 과정을 효율적으로 진행합니다. 실제 구현 과정에서
다음 단계를 따릅니다.
- 각 노드에 대한 최단 거리 배열을 초기화합니다. 초기값은 무한대로 설정하되, 시작 노드의 거리는 0으로 설정합니다.
- 우선순위 큐(미니 힙)를 사용하여 시작 노드를 큐에 추가합니다.
- 큐가 비어있지 않을 때까지 반복합니다.
- 큐에서 가장 짧은 거리를 가진 노드를 꺼내고, 해당 노드와 인접한 노드들에 대해
거리를 갱신합니다. 만약 새로운 거리 값이 기존 거리보다 작으면 우선순위 큐에 추가합니다. - 모든 노드에 대한 최단 거리를 계산한 후 배열을 반환합니다.
자바스크립트 구현
이제 위의 알고리즘을 바탕으로 실제 문제를 해결하는 자바스크립트 함수를 구현해 보겠습니다.
function dijkstra(n, edges, start) {
// 1. 그래프 구성
const graph = Array.from({ length: n + 1 }, () => []);
for (const [u, v, weight] of edges) {
graph[u].push({ node: v, weight });
graph[v].push({ node: u, weight }); // 무방향
}
// 2. 최단 거리 초기화
const distance = Array(n + 1).fill(Infinity);
distance[start] = 0;
// 3. 우선순위 큐 초기화
const pq = new MinHeap();
pq.insert({ node: start, weight: 0 });
while (!pq.isEmpty()) {
const { node: currentNode, weight: currentWeight } = pq.extractMin();
if (currentWeight > distance[currentNode]) continue;
// 4. 인접 노드 처리
for (const { node: neighbor, weight } of graph[currentNode]) {
const newDistance = currentWeight + weight;
if (newDistance < distance[neighbor]) {
distance[neighbor] = newDistance;
pq.insert({ node: neighbor, weight: newDistance });
}
}
}
return distance.slice(1); // 시작 노드를 제외한 거리 배열 반환
}
// 미니 힙 클래스 (우선순위 큐 구현)
class MinHeap {
constructor() {
this.heap = [];
}
insert({ node, weight }) {
this.heap.push({ node, weight });
this.bubbleUp();
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].weight >= this.heap[parentIndex].weight) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin() {
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
bubbleDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild.weight < element.weight) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild.weight < element.weight) ||
(swap !== null && rightChild.weight < leftChild.weight)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
isEmpty() {
return this.heap.length === 0;
}
}
테스트
위 코드를 테스트하기 위해 다음과 같이 함수를 호출하여 결과를 확인할 수 있습니다.
const n = 6;
const edges = [
[1, 2, 1],
[1, 3, 4],
[2, 3, 2],
[2, 4, 5],
[3, 4, 1],
[4, 5, 3],
[3, 5, 6],
[5, 6, 2],
[4, 6, 1]
];
const start = 1;
const distances = dijkstra(n, edges, start);
console.log(distances); // [0, 1, 3, 4, 6, 7]
결론
다익스트라 알고리즘은 최단 경로를 찾는 데 매우 유용한 알고리즘입니다. 이 강좌에서
다룬 문제와 코드를 통해 다익스트라 알고리즘의 기본 개념과 자바스크립트에서의
구현 방법에 대해 이해할 수 있었기를 바랍니다. 알고리즘에 대한 더 깊은 이해는
실제 코딩 테스트와 문제 해결 능력을 향상하는 데 도움이 됩니다.
앞으로도 다양한 알고리즘을 공부하고 연습해보세요!