- 지난 알고리즘 글에서 다익스트라 알고리즘을 정리한 글을 작성한다 예고했었다.
- 다익스트라 알고리즘의 구현 방법 및, 실제 문제 풀이를 정리해보고자 한다.
다익스트라 알고리즘(Dijkstra's Algorithm)
: 그래프 상의 두 정점 사이의 최단거리를 구하는 알고리즘.
- GPS, 네트워크 라우팅 등의 다양한 분야에서 활용된다.
다익스트라 알고리즘 구현
다익스트라 알고리즘은 다음과 같은 과정을 거친다.
- 시작점에서 탐색을 시작한다.
- 새 노드에 방문할 때마다, 가장 작은 거리(가중치)를 갖는 노드를 골라서 방문한다.
- 방문한 노드의 각 인접점에 대해, 시작점까지의 거리를 계산한다.
→ 이 때, 새로운 최단거리가 나오면 최단거리를 업데이트 한다.
이전에 다른 글에서 정리한 그래프와 달리, 다익스트라 알고리즘의 구현을 위해서는 간선의 가중치(Weight)를 기록해야할 필요성이 있으며, 노드에 방문할 때마다 가장 가까운 노드를 방문해야 하기 때문에 인접점을 가까운 순으로 정렬할 필요성도 있다.
간선의 가중치를 기록하기 위해선 아래와 같이, 그래프를 구성할 때 가중치를 추가로 넣어주면 된다.
// 가중 무방향 그래프의 구현
class WeightedGraph {
constructor (num) { // 그래프의 정점을 초기화한다
this.adjacencyList = {};
for (let i = 1; i <= num; i++) {
this.adjacencyList[i] = [];
}
}
addEdge (v1, v2, weight) { // 간선 추가 시, 가중치도 함께 저장한다
this.adjacencyList[v1].push({ node: v2, weight });
this.adjacencyList[v2].push({ node: v1, weight });
}
}
노드에 방문할 때마다 가장 가까운 노드에 방문해야 하기 때문에, 가중치를 이용하는 우선순위 큐를 사용한다.
우선순위 큐의 구현에는 지난 게시물에서 작성하였듯 이진 힙을 사용하는 방법도 있지만, 아래와 같이 sort함수를 사용해서 간단히 순위를 기준으로 정렬하는 방법을 사용할 수도 있다.
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(el) {
this.queue.push(el);
this.sort();
}
dequeue() {
return this.queue.shift();
}
sort() {
this.queue.sort((a, b) => a.weight - b.weight);
}
}
위의 점을 고려하여 실제로 다익스트라 알고리즘을 구현한다고 할 때, 다음과 같은 과정을 거치게 된다.
- 탐색에 사용할 우선순위 큐 및, 시작점에서 각 정점까지의 최단거리를 기록할 distances 객체(or 배열)를 만든다.
- 그래프의 각 정점을 우선순위 큐에 넣는다. 이 때, 시작점의 가중치를 0, 나머지 정점의 가중치를 Infinity로 설정하여 시작점을 가장 먼저 탐색하도록 한다.
- distances 또한 시작점을 제외한 나머지 정점들까지의 거리를 Infinity로 초기화 한다. 시작점에서 시작점까지의 거리는 0이므로 0으로 초기화한다.
- 우선순위 큐에 남은 요소가 없을 때까지 반복을 진행한다.
- 우선순위 큐에서 현재 정점과 현재 정점에서 시작점까지의 거리를 꺼내고, 인접점을 탐색한다.
- 현재 정점에서 인접점 까지의 거리 + 현재 정점에서 시작점까지의 거리(큐에서 꺼낸 것)를 distances에 저장된 거리와 비교한다.
- 위에서 만약 새로운 거리가 저장된 최단거리보다 짧으면, distances를 갱신하고 다시 현재 정점과 새로운 최단거리를 큐에 넣는다.
- 큐에 남은 요소가 없거나, 도착 정점이 있고 해당 도착정점에 도달한 경우 반복을 중단한다.
// 시작 접점을 1로 하는 다익스트라 알고리즘
const priorityQueue = new PriorityQueue();
const distances = {}; // 최단거리를 기록하는 객체
const adjacencyList = /* ... */; // 정점들 간 간선과 가중치 정보가 담긴 인접 리스트
for (let vertex in adjacencyList) {
if (vertex === '1') {
distances[vertex] = 0;
priorityQueue.euqueue({ node: vertex, weight: 0 }); // 시작 정점을 큐에 넣는다
} else {
distances[vertex] = Infinity;
priorityQueue.euqueue({ node: vertex, weight: Infinity });
}
}
while (priorityQueue.queue.length > 0) {
const current = priorityQueue.dequeue();
for (let v in adjacencyList[current.node]) {
const neighbor = adjacencyList[current.node][v];
const newDistance = neighbor.weight + distances[current.node];
// 새로운 최단거리가 나올 경우, 최단거리 갱신 후 우선순위 큐에 넣는다
if (newDistance < distances[neighbor.node]) {
distances[neighbor.node] = newDistance;
queue.enqueue({ node: neighbor.node, weight: newDistance });
}
}
}
실제 문제 풀이
백준 1916번
한 도시에서 다른 도시까지 가는 데에 드는 최소 비용을 구하는 문제. 주어지는 도시 사이의 버스 정보를 그래프로 나타내면 방향 가중 그래프가 되므로 이를 고려하여 그래프를 생성해야한다. 그 이후론 일반적인 다익스트라 알고리즘을 사용해서 답을 구하면 된다. 처음으로 풀어보는 다익스트라 알고리즘 문제라, 강의에서 공부한 코드를 써보는 것(우선순위 큐를 포함해서)에 집중한 나머지 답안 코드가 좀 길어졌다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
class Node {
constructor (value, priority) {
this.value = value;
this.priority = priority;
}
}
class PriorityQueue {
constructor () {
this.queue = [];
}
enqueue (value, priority) {
const newNode = new Node(value, priority);
this.queue.push(newNode);
this.bubbleUp();
}
bubbleUp () {
let idx = this.queue.length - 1;
let node = this.queue[idx];
while (idx > 0) {
const parentIdx = Math.floor(idx / 2);
const parentNode = this.queue[parentIdx];
if (node.priority >= parentNode.priority) break;
this.queue[parentIdx] = node;
this.queue[idx] = parentNode;
idx = parentIdx;
}
}
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;
}
bubbleDown () {
let idx = 0;
let node = this.queue[0];
const length = this.queue.length;
while (true) {
// 나보다 작은 priority의 자식을 위에 올려야 함
const leftChildIdx = 2 * idx + 1;
const rightChildIdx = 2 * idx + 2;
let toSwap = null;
if (leftChildIdx < length) {
if (this.queue[leftChildIdx].priority < node.priority) {
toSwap = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(toSwap === null && this.queue[rightChildIdx].priority < node.priority) ||
(toSwap !== null && this.queue[rightChildIdx].priority < this.queue[toSwap].priority)
) {
toSwap = rightChildIdx;
}
}
if (toSwap === null) break;
this.queue[idx] = this.queue[toSwap];
this.queue[toSwap] = node;
idx = toSwap;
}
}
}
class WeightedGraph {
constructor(num) {
this.adjacencyList = {};
for (let i = 1; i <= num; i++) {
this.adjacencyList[i] = [];
}
}
addEdge(start, end, weight) {
this.adjacencyList[start].push({ node: end.toString(), weight });
}
dijkstra (start, finish) {
const priorityQueue = new PriorityQueue();
const distances = {}; // 각 점까지의 최소 거리
const previous = {};
let smallest;
for (let vertex in this.adjacencyList) {
if (vertex === start) {
distances[vertex] = 0;
priorityQueue.enqueue(vertex, 0);
} else {
distances[vertex] = Infinity;
priorityQueue.enqueue(vertex, Infinity);
}
previous[vertex] = null;
}
while (priorityQueue.queue.length) {
smallest = priorityQueue.dequeue().value;
if (smallest === finish) {
break;
}
if (smallest || distances[smallest] !== Infinity) {
for (let n in this.adjacencyList[smallest]) {
const next = this.adjacencyList[smallest][n];
const newDistance = distances[smallest] + next.weight;
if (newDistance < distances[next.node]) {
distances[next.node] = newDistance;
previous[next.node] = smallest;
priorityQueue.enqueue(next.node, newDistance);
}
}
}
}
return distances[finish];
}
}
rl.on("line", (line) => {
input.push(line);
}).on("close", function () {
const n = parseInt(input.shift());
const m = parseInt(input.shift());
const graph = new WeightedGraph(n);
for (let i = 0; i < m; i++) {
const [start, end, weight] = input[i].split(' ').map((el) => parseInt(el));
graph.addEdge(start, end, weight);
}
const [start, end] = input[input.length - 1].split(' ');
const answer = graph.dijkstra(start, end);
console.log(answer);
process.exit();
});
프로그래머스 배달 문제
역시나 다익스트라 알고리즘을 활용할 수 있는 문제. 각 마을 사이의 거리 정보가 주어지고, 1번 마을에서 배달을 갈 수 있는 마을이 몇 개인지 구하는 문제이다. 위의 문제와 달리 가중 무방향 그래프를 그리되, 1번 마을에서 갈 수 있는 모든 마을들을 다 살펴야 하므로 우선순위 큐의 내용물이 없을 때까지 탐색을 반복하면 된다.
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(el) {
this.queue.push(el);
this.sort();
}
dequeue() {
return this.queue.shift();
}
sort() {
this.queue.sort((a, b) => a.weight - b.weight);
}
}
function solution(N, road, K) {
var answer = 0;
const queue = new PriorityQueue();
const distances = {};
const adjacencyList = {};
for (let i = 1; i <= N; i++) {
if (i === 1) distances[i] = 0;
else distances[i] = Infinity;
adjacencyList[i] = [];
}
for (let i = 0; i < road.length; i++) {
const [v1, v2, weight] = road[i];
adjacencyList[v1].push({ node: v2, weight });
adjacencyList[v2].push({ node: v1, weight });
}
queue.enqueue({ node: 1, weight: 0 });
// 시작점을 1로 한 다익스트라
while (queue.queue.length > 0) {
const { node: currentNode, weight: currentDistance } = queue.dequeue();
for (let v in adjacencyList[currentNode]) {
const neighbor = adjacencyList[currentNode][v];
const newDistance = neighbor.weight + distances[currentNode];
if (newDistance < distances[neighbor.node]) {
distances[neighbor.node] = newDistance;
queue.enqueue({ node: neighbor.node, weight: newDistance });
}
}
}
Object.values(distances).forEach((el) => {
if (el <= K) answer++;
});
return answer;
}
여기서는 백준 문제와 달리 우선순위 큐 작성에 sort함수를 사용하였다. 순위가 우선되는 요소를 앞에 배치하기 위해 이진 힙을 활용하여 정렬을 하는 것인데, 자바스크립트에서는 이 부분을 다 구현해야 하니 실제 코딩테스트라면 시간이 빠듯할 수도 있겠다는 생각이 들었기 때문이다. 이진 힙 구현부분이 길다보니 아무래도 이쪽이 좀 더 부담이 적었다.
- 그래프 문제는 워낙 중요하다 보니 문제를 많이 접하고 있다. 그만큼 처음보다 조금은 익숙해진 느낌인데, 다익스트라 알고리즘도 문제를 꾸준히 풀어보며 숙련도를 높여야겠다.
'공부 > 알고리즘' 카테고리의 다른 글
| Monotonic Stack에 대하여 (0) | 2024.04.14 |
|---|---|
| 이진 힙(Binary Heap) 정리 (0) | 2023.12.19 |
| 문자열 문제 풀이 (0) | 2023.12.11 |
| 구현 문제 풀이 (1) | 2023.12.04 |
| 그래프 & DFS/BFS 문제 풀이 (2) | 2023.11.19 |
