🎲 백준 1162번 도로포장

백준 1162번

🧸 이번 문제를 풀면서 다익스트라 알고리즘에서 놓치고 있던 부분까지 확실하게 알게 된 것 같다. 그리고 힙을 사용해 우선순위 큐를 구현하는 방법을 참고 코드 없이 구현하기위해서 많은 연습이 필요할 것 같다. 다음은 우선 순위 큐 문제를 풀어 익숙해지는 시간을 가져야겠다.
💡 포장 도로 개수를 따로 배열로 만들어야한다.
🎨 우선순위 큐
🎨 참고 코드

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M, K] = input.shift().split(" ").map(Number);
const road = Array.from(new Array(N + 1), () => []);
for (let m = 0; m < M; m++) {
  const [a, b, c] = input[m].split(" ").map(Number);
  road[a].push([b, c]);
  road[b].push([a, c]);
}

class Heap {
  constructor() {
    this.heap = [];
  }
  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

  insert = (data) => {
    this.heap.push(data);
    this.heapifyUp();
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[parentIndex][1] > lastInsertedNode[1]) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else break;
    }

    this.heap[index] = lastInsertedNode;
  };

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return rootNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex][1] < this.heap[leftChildIndex][1]
          ? rightChildIndex
          : leftChildIndex;

      if (this.heap[smallerChildIndex][1] <= rootNode[1]) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
}

class PriorityQueue extends Heap {
  constructor() {
    super();
  }

  isEmpty() {
    return this.heap.length <= 0;
  }

  insert(data) {
    this.insert(data);
  }

  remove() {
    this.remove();
  }

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

const dijkstra = () => {
  const distArr = Array.from(new Array(N + 1), () =>
    new Array(K + 1).fill(Infinity)
  );
  const queue = new PriorityQueue();
  queue.insert([1, 0, 0]);
  distArr[1][0] = 0;

  while (queue.length()) {
    const [city, total, paved] = queue.remove();

    if (distArr[city][paved] < total) continue;

    for (let i = 0; i < road[city].length; i++) {
      const [nextCity, dist] = road[city][i];
      const nextTotal = total + dist;

      if (nextTotal < distArr[nextCity][paved]) {
        distArr[nextCity][paved] = nextTotal;
        queue.insert([nextCity, nextTotal, paved]);
      }
      if (paved < K && total < distArr[nextCity][paved + 1]) {
        distArr[nextCity][paved + 1] = total;
        queue.insert([nextCity, total, paved + 1]);
      }
    }
  }
  return Math.min(...distArr[N]);
};

console.log(dijkstra());