[다익스트라][백준] 117799 최소비용 구하기2 JS

문제링크

 

한 노드에서 다른 노드까지의 최소 비용을 구하는 것이기 때문에 다익스트라!

 

다익스트라 : 한 정점에서 다른 모든 정점까지의 최소 비용을 구하는 알고리즘

 

다익스트라는 우선순위큐를 사용하는데

JS에는 우선순위큐 라이브러리가 없기 때문에 직접 구현

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

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

 

 

 

 

 

풀이 코드

우선순위 큐 구현 코드는 페이지 가장 하단에 있습니다!!

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

// 입력값이 첫 번째 줄에는 입력 값의 길이(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);

 

 

 

우선순위 큐 구현 코드

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;
  }
}