JavaScript 코딩테스트 - 빠른 다익스트라 (with 우선순위 큐)

코딩 테스트 대비 저장용 포스트입니다.

BOJ 1753번: 최단경로 문제

"use strict";

class MinHeap {
  constructor() {
    this.heap = [];
    this.compare = (child, parent) => parent.dist <= child.dist;
  }

  swap(indexA, indexB) {
    [this.heap[indexA], this.heap[indexB]] = [this.heap[indexB], this.heap[indexA]];
  }

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

  push(value) {
    this.heap.push(value);
    this.upHeap();
    return this.heap.length;
  }

  pop() {
    if (this.heap.length === 0) {
      return undefined;
    }
    this.swap(0, this.heap.length - 1);
    const value = this.heap.pop();
    this.downHeap(0);
    return value;
  }

  upHeap() {
    let current = this.heap.length - 1;

    while (0 < current) {
      const parent = Math.floor((current - 1) / 2);
      if (this.compare(this.heap[current], this.heap[parent])) {
        return;
      }
      this.swap(parent, current);
      current = parent;
    }
  }

  downHeap(idx) {
    let current = idx;

    while (current < this.heap.length) {
      // CBT 구조 특징 : 특정 idx의 자식 노드 -> idx*2+1, idx*2+2
      let leftChild = current * 2 + 1;
      let rightChild = current * 2 + 2;

      if (this.heap[leftChild] === undefined) {
        break;
      }
      if (this.heap[rightChild] === undefined) {
        if (this.compare(this.heap[leftChild], this.heap[current])) {
          break;
        }
        this.swap(current, leftChild);
        current = leftChild;
        continue;
      }
      // 오른쪽거가 더 작으면 true
      const nextChild = this.compare(this.heap[leftChild], this.heap[rightChild]) ? rightChild : leftChild;
      if (this.compare(this.heap[nextChild], this.heap[current])) {
        break;
      }
      this.swap(current, nextChild);
      current = nextChild;
    }
  }
}

const [nm, stt, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const [N, M] = nm.split(" ").map(Number);
const startNode = Number(stt);
const paths = arr.map((s) => s.split(" ").map(Number));
const pq = new MinHeap();
const adj = new Map(Array.from({ length: N }, (_, i) => [i + 1, []]));
const distFromStart = Array(N + 1).fill(Infinity);

paths.forEach(([stt, dest, d]) => {
  adj.get(stt).push([dest, d]);
});

distFromStart[startNode] = 0;
pq.push({ dist: 0, node: startNode });

while (pq.size()) {
  const { dist, node } = pq.pop();

  if (distFromStart[node] !== dist) {
    continue;
  }

  if (!adj.has(node)) {
    continue;
  }

  adj.get(node).forEach(([nextNode, nextDist]) => {
    if (distFromStart[nextNode] <= dist + nextDist) {
      return;
    }
    distFromStart[nextNode] = dist + nextDist;
    pq.push({ dist: Number(dist + nextDist), node: nextNode });
  });
}

console.log(
  distFromStart
    .slice(1)
    .map((d) => (d === Infinity ? "INF" : d))
    .join("\n")
);