boj 11779 js 최소비용 구하기2

한 노드에서 다른 노드까지의 최소 비용을 구하는 것이기 때문에 다익스트라!
JS에는 우선순위큐 라이브러리가 없기 때문에 직접 구현

접근 방법
1. 버스 정보 인접리스트, 각 노드까지의 비용을 저장할 배열(minArr), 이전에 방문한 노드를 저장할 배열(pre)을 만든다.
2. 우선순위 큐에 시작 노드를 넣어준다
3. 큐가 빌 때까지 노드를 꺼내서 minArr와 pre배열을 업데이트 한다

3번에서 배열들을 업데이트 할 때
1. minArr에 있는 값이 우선순위 큐에서 꺼낸 값보다 작을 경우, 꺼낸 값은 최소 비용이 아님으로 continue;
2. minArr에 있는 값보다 우선순위 큐에서 꺼낸 값이 작은 경우, 현재 기준에서 제일 최소 비용이므로 minArr의 값을 업데이트 해준다.
또한 큐에서 꺼낸 노드가 최소 비용인 상태이므로 인접한 노드들의 비용도 확인한다.
(현재 노드의 비용 + 현재 노드에서 인접 노드까지의 비용)을 minArr 값과 비교해서 더 작은 경우에는 인접 노드의 minArr와 pre배열을 업데이트 하고 우선순위 큐에 넣어준다.

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.priority < element.priority) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild.priority < element.priority) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
  }
}

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
//입력값 1개(1줄)
// const input = require('fs').readFileSync(filePath).toString().trim();

//입력값 여러개 (1줄)
// let input = require('fs').readFileSync(filePath).toString().trim().split(' ');

//입력값 여러 줄
// let input = require('fs').readFileSync(filePath).toString().trim().split('\n');

// 입력값이 첫 번째 줄에는 입력 값의 길이(n), n개의 줄에 걸쳐서 한 줄에 하나의 입력값이 주어질 때
const [n, m, ...input] = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');

function solution(N, M, Routes, SE) {
  //최소값배열
  const minArr = new Array(N + 1).fill(Infinity);

  //경로 탐색 - 이전 노드
  const pre = new Array(N + 1).fill(0);
  const pq = new PriorityQueue();
  const adjacencyList = {};
  const [start, end] = SE;
  const answerRoute = [];

  Routes.forEach(([start, end, weight]) => {
    if (!adjacencyList[start]) adjacencyList[start] = [];
    if (!adjacencyList[end]) adjacencyList[end] = [];

    adjacencyList[start].push({ end, weight });
  });

  minArr[start] = 0;
  pq.enqueue(start, 0);

  while (pq.values.length) {
    const { val, priority } = pq.dequeue();

    if (minArr[val] < priority) continue;
    minArr[val] = priority;

    adjacencyList[val]?.forEach((item) => {
      const { end, weight } = item;
      if (priority + weight < minArr[end]) {
        minArr[end] = priority + weight;
        pre[end] = val;
        pq.enqueue(end, minArr[end]);
      }
    });
  }

  function findPre(start, end) {
    answerRoute.push(end);
    if (start === end) return;

    return findPre(start, pre[end]);
  }

  findPre(start, end);

  return [
    minArr[end],
    answerRoute.length,
    answerRoute.reverse().join(' '),
  ].join('\n');
}

const depArr = input.splice(-1);
const answer = solution(
  Number(n),
  Number(m),
  input.map((item) => item.split(' ').map(Number)),
  depArr[0].split(' ').map(Number),
);

console.log(answer);

참고 : https://youtu.be/o9BnvwgPT-o?si=CjyWKoj8SAXmYVgS