문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1

0
2
3
7
INF

나의 코드

const inputFileName =
  process.platform === "linux" ? "/dev/stdin" : "example.txt";

const input = require("fs")
  .readFileSync(inputFileName)
  .toString()
  .trim()
  .split("\n")
  .map((r) => r.split(" ").map(Number));

const [[V, E], [K], ...nodes] = input;

// 각 노드의 인접노드를 2차원 배열 형태로 저장할 빈 배열 선언
let graph = Array.from({ length: V + 1 }, () => []);
// 각 노드까지의 최단 거리를 memo할 DP table 역할을 함. Infinity로 채워둔다.
let distance = Array.from({ length: V + 1 }, () => Infinity);

// 우선순위 큐 필요할 때 요긴하게 써먹을 class
class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(item, priority) {
    const node = { item, priority };
    let i = 0;

    while (i < this.heap.length && this.heap[i].priority <= priority) {
      i++;
    }

    this.heap.splice(i, 0, node);
  }

  dequeue() {
    return this.heap.shift();
  }

  get length() {
    return this.heap.length;
  }
}

// graph의 각 원소(배열 형태)에 각 노드의 인접노드를 push.
for (let [u, v, w] of nodes) {
  graph[u].push([v, w]);
}

// 다익스트라 알고리즘
function dijkstra(startNode) {
  const pq = new PriorityQueue();
  pq.enqueue(startNode, 0);
  distance[startNode] = 0;

  while (pq.length) {
    const { item: node, priority: dist } = pq.dequeue();

    const adj = graph[node];
    for (let i = 0; i < adj.length; i++) {
      let cost = dist + adj[i][1];

      if (cost < distance[adj[i][0]]) {
        distance[adj[i][0]] = cost;
        pq.enqueue(adj[i][0], cost);
      }
    }
  }
}

dijkstra(K);

// console 출력
for (let i = 1; i < V + 1; i++) {
  console.log(distance[i] === Infinity ? "INF" : distance[i]);
}

오늘은 대빵 긴 코드 ㅎㅎㅎㅎㅎ...
미루고 미뤄왔던 다익스트라를 공부해봤는데 알고리즘을 풀면서 실제로 class를 써보는 건 처음이었다.
사실 node.js에서 사용할 수 있는 js-priority-queue라는 게 있다길래 한 번 사용해봤는데 와우 완전 신세계잖아!! 그런데 음.. 백준에 제출하니 에러가 뜨네 ^_^

런타임 에러 (CannotFindModule)

이런 라이브러리를 처음 써보니 아주 신세계였기 때문에, 비록 통과는 안 됐지만 라이브러리 사용법은 한번 리뷰를 해보자 ㅋㅋㅋㅋ

js-priority-queue 사용법

// js-priority-queue 라이브러리를 가져와서 PriorityQueue 변수에 할당
const PriorityQueue = require("js-priority-queue");

// comparator 옵션을 사용하여 두 요소의 우선순위를 비교하는 함수를 정의(min heap)
const q = new PriorityQueue({ comparator: (a, b) => a.dist - b.dist });

// enqueue
q.queue({ node: startNode, dist: 0 });
 
// dequeue
const { node, dist } = q.dequeue();

알고리즘 풀 때 아니면 언제 사용하게 될 지 아직은 잘 모르겠지만, 써보니까 아주 편해서 깜짝 놀랐다. ㅋㅋㅋ 이건 마치 신문물을 접한 사람 ㅋㅋㅋㅋㅋ 근데 그럼 뭐하냐고 막상 제출이 안되는데 ㅠㅠ

파이썬은 우선순위 큐 구할 때 heapq 라이브러리 사용하던데 js는 그럼 우선순위 큐 써야할 때 무조건 class로 구현해야하는 것인가? 아직은 class 외에는 다른 방법을 모르겠다. 그래서 일단은 class로 구현을 해보았다.

근데 막상 라이브러리 못쓴다고 투덜투덜했지만 막상 class로 구현해보니 이 끌래스 요긴하게 쓰일 것 같은데? 이 문제 자세히 공부해보고 나중에 다른 다익스트라 알고리즘 문제들도 풀어봐야겠다.

여튼 각설하고 오늘의 코드 리뷰를 해보좌!!

• dijkstra 함수
• PriorityQueue 클래스

순서대로 리뷰를 해보겠다.

function dijkstra(startNode) {
  const pq = new PriorityQueue();
  pq.enqueue(startNode, 0);
  distance[startNode] = 0;

  while (pq.length) {
    const { item: node, priority: dist } = pq.dequeue();
    
    const adj = graph[node];
    for (let i = 0; i < adj.length; i++) {
      let cost = dist + adj[i][1];

      if (cost < distance[adj[i][0]]) {
        distance[adj[i][0]] = cost;
        pq.enqueue(adj[i][0], cost);
      }
    }
  }
}

dijkstra(K);

PriorityQueue 클래스를 이용하여 pq라는 인스턴스를 생성한다.
pq에는 heap이라는 프로퍼티가 있고, 값은 빈 배열이다.
이 배열이 바로 우선순위 큐를 구현하는데 핵심이 되어줄 친구이다.

K는 1이고 startNode에 인자로 전달하면, pq에 (1, 0)을 전달하여 enqueue한다.
여기서 1은 시작노드 번호이고, 0은 시작 노드부터 해당 노드까지의 비용(또는 거리)를 의미한다.

그리고 원본 코드에서는 distance = [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]를 위에서 정의해놓고 시작했는데, 이는 반복문을 돌리면서 시작 노드로부터 각 노드까지의 거리를 계속 갱신할 DP table의 역할을 한다. 시작 노드인 1번 노드의 distance는 0이므로 우선 갱신하고 시작!

startNode 갱신 후

distance = [Infinity, 0, Infinity, Infinity, Infinity, Infinity]

이제 돌려돌려 while문 차례.
매 회차마다 현재 노드로부터 거리가 가장 짧은 노드를 우선순위 큐에서 꺼내는 것이다.

현재 노드: 1번 노드

const { item: node, priority: dist } = pq.dequeue();

pq에 노드가 하나 밖에 없었으니 dequeue해오면 1번 노드가 나올 것이다.

1번 노드의 인접 노드는 2, 3이고 adj = [[2, 2], [3, 3]]이다. (위에서 graph 배열에 각 노드의 인접 노드를 미리 담아놨었다.)
이 adj를 순회하면서 distance 배열을 갱신할 필요가 있는지 살펴보자.

2번 노드의 경우 cost = 0 + 2이다.
여기서 0은 1번 노드까지의 비용이므로, 지금까지의 결과로는 2번 노드까지 가는 최단 거리(cost)가 2이다. 이 cost는 distance의 2번째 인덱스에 있던 Infinity보다 작으므로 배열을 갱신한다.
3번 노드도 마찬가지로 cost = 0 + 3이다.
따라서 3번 노드도 갱신한다.

distance = [Infinity, 0, 2, 3, Infinity, Infinity]

그리고 (2, 2)와 (3, 3)을 pq에 enqueue한다.

pq = (2, 2), (3, 3)

현재 노드: 2번 노드

2번 노드와 3번 노드가 pq에 들어있고, 밑에서 자세히 살펴보겠지만, class에서 구현된 min heap 로직에 따라 2번 노드가 현재 노드로 선택된다.

2번 노드의 인접 노드는 3, 4이고, adj = [[3, 4], [4, 5]]이다.
adj를 순회하면서 distance 배열을 갱신할 필요가 있는지 살펴보자.

3번 노드의 경우 cost = 2 + 4이다. 현재 거리가 3이므로 6은 3보다 커서 무시한다.
4번 노드의 경우 cost = 2 + 5이다. 7은 Infinity보다 작으므로 배열을 갱신한다.

distance = [Infinity, 0, 2, 3, 7, Infinity]

그리고 (4, 7)을 pq에 enqueue한다.

pq = (3, 3), (4, 7)

현재 노드: 3번 노드

마찬가지로 3번 노드가 4번보다 거리가 더 짧으므로 3번 노드가 현재 노드가 된다.

3번 노드의 인접노드는 4번 노드이고, adj = [[4, 6]]이다.

4번 노드의 경우 cost = 3 + 6인데, 이미 기존 최단 거리인 7이 더 작으므로 9라는 숫자는 무시한다.

distance도 갱신할 필요가 없다.
pq에도 enqueue할 노드가 없다.

pq = (4, 7)

현재 노드: 4번 노드

4번 노드의 인접 노드는 없다.
따라서 enqueue할 것이 더 이상 없고, pq의 길이가 0이 되어 반복문이 종료된다.

그래서 최종적으로 distance 배열을 보면

distance = [Infinity, 0, 2, 3, 7, Infinity]

이고,
1번 노드부터 차례대로 출력하면 답이 되는 것이다. (물론 Infinity일 때는 문제에서 요구한대로 "INF"라는 문자열로 바꿔줘야 한다.)

이제 대망의 PriorityQueue 클래스를 살펴보자. 어떻게 구현되어 있길래 enqueue, dequeue, length까지 인터페이스의 역할을 해내고 있는 것일까?

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

// enqueue : heap 배열의 원소들을 하나씩 확인하여 자기가 누울 자리를 찾음
  enqueue(item, priority) {
    const node = { item, priority };
    let i = 0;

    while (i < this.heap.length && this.heap[i].priority <= priority) {
      i++;
    }

    this.heap.splice(i, 0, node);
  }

// 우선순위가 높은 원소 순서대로 앞에서부터 있으므로 shift()한다.
  dequeue() {
    return this.heap.shift();
  }
// heap 배열의 length를 return함.
  get length() {
    return this.heap.length;
  }
}

dequeue와 get length()는 아주 간단하군.

enqueue를 구현하는 로직이 신기하다. ㅎㅎㅎ
heap 배열의 0번째 원소부터 순회하면서
out of range 되지 않고 && i번째 원소보다 node의 우선순위가 낮으면 점점 뒤로 밀려나는 식이다.
이렇게 i번째 노드보다 우선순위가 높을 때까지 밀려난 다음, i번째에서 splice를 이용하여 node를 삽입한다.

이렇게 코드를 하나씩 뜯어보니까 다익스트라 알고리즘의 원리는 머릿속에 잘 저장된 것 같다.
다른 다익스트라 문제들도.. 잘 풀 수 있으려나?!
계속 도전해보자 ㅎㅎㅎ
화이팅!!