백준 node.js 1916번 최소비용 구하기 다익스트라 알고리즘 JavaScript JS

1916번: 최소비용 구하기

😉문제 설명

이 문제는 단순한 다익스트라 문제이지만, 주의해야 할 부분이 몇가지 있습니다.

1. 하나의 출발 지점에서 하나의 다른 도착 지점으로 가는 버스 노선이 여러 개 일 수 있습니다. 따라서 최소 비용을 가진 노선만 간선에 넣어주어야 합니다. (모든 노선을 넣으면 시간 초과가 납니다.)
2. 비용이 0인 간선이 있습니다. 아래 코드는 틀린 코드와 맞는 코드입니다. 0은 falsy값 이기 때문에 주의가 필요합니다.

틀린 코드

const links = Array.from({ length: N + 1 }, () => ({}));
for (let i = 2; i < M + 2; i++) {
  const [str, end, cost] = input[i].split(" ").map(Number);
  if(! links[str][end] || links[str][end] > cost) links[str][end] = cost;
} //비용이 0 일 때도 값이 바뀌어 버린다.

맞는 코드

const links = Array.from({ length: N + 1 }, () => ({}));
for (let i = 2; i < M + 2; i++) {
  const [str, end, cost] = input[i].split(" ").map(Number);
  if(links[str][end] === undefined || links[str][end] > cost) links[str][end] = cost;
}

😎문제 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split("\\n");
const [N, M] = [input[0], input[1]].map(Number);
const links = Array.from({ length: N + 1 }, () => ({}));
for (let i = 2; i < M + 2; i++) {
  const [str, end, cost] = input[i].split(" ").map(Number);
  if(links[str][end] === undefined || links[str][end] > cost) links[str][end] = cost;
}
const [strCity, endCity] = input[M + 2].split(" ").map(Number);

// 우선순위 큐
class minHeap {
  constructor() {
    this.heap = [];
  }
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parrentIndex = Math.floor(currentIndex / 2);
    while (
      currentIndex !== 0 &&
      this.heap[parrentIndex].cost > this.heap[currentIndex].cost
    ) {
      this.heap[currentIndex] = { ...this.heap[parrentIndex] };
      this.heap[parrentIndex] = value;
      currentIndex = parrentIndex;
      parrentIndex = Math.floor(currentIndex / 2);
    }
  }
  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const returnValue = { ...this.heap[0] };
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;
    let leftIndex = 1;
    let rightIndex = 2;
    while (
      (this.heap[leftIndex] &&
        this.heap[leftIndex].cost < this.heap[currentIndex].cost) ||
      (this.heap[rightIndex] &&
        this.heap[rightIndex].cost < this.heap[currentIndex].cost)
    ) {
      if (
        this.heap[leftIndex] === undefined ||
        (this.heap[rightIndex] &&
          this.heap[rightIndex].cost < this.heap[leftIndex].cost)
      ) {
        const temp = { ...this.heap[rightIndex] };
        this.heap[rightIndex] = { ...this.heap[currentIndex] };
        this.heap[currentIndex] = temp;
        currentIndex = rightIndex;
        leftIndex = currentIndex * 2 + 1;
        rightIndex = currentIndex * 2 + 2;
      } else {
        const temp = { ...this.heap[leftIndex] };
        this.heap[leftIndex] = { ...this.heap[currentIndex] };
        this.heap[currentIndex] = temp;
        currentIndex = leftIndex;
        leftIndex = currentIndex * 2 + 1;
        rightIndex = currentIndex * 2 + 2;
      }
    }
    return returnValue;
  }
}

// 다익스트라
const costArr = Array(N + 1).fill(Infinity);
costArr[strCity] = 0;
const Q = new minHeap();
Q.push({ cur: strCity, cost: 0 });

while (Q.heap.length > 0) {
  const { cur } = Q.pop();
  for (let next of Object.keys(links[cur])) {
    const cost = links[cur][next]
    if (costArr[next] > costArr[cur] + cost) {
      costArr[next] = costArr[cur] + cost;
      Q.push({ cur: next, cost: costArr[next] });
    }
  }
}

console.log(costArr[endCity]);