Node.js) 백준 1753번 : 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

다익스트라 알고리즘 => 힙

 

 

 시간초과가 계속 나와서  예전에 썻던 방법으로 readline 모듈로 바꿔줘고, 코드에 썼던 배열도 다 큐로 바꿔줬는데 풀 수가 없었습니다. 

 

 결국 질문하기 들어가서 보니까 큐가 아니라 힙을 이용해 푸는 문제였습니다. 

(https://www.acmicpc.net/board/view/71956  옆에 링크에 고수분들이 잘 설명해주셨습니다. )

 

큐는 대충  필요한 만큼만 빨리 구현할 수 있는데, 힙을 구현하려고 하니까 갑자기 피곤해졌습니다. 🥱

이럴때면 힙을 손수 구현할 필요가 없는 파이썬이 참 부럽습니다. 😒

 

그냥 예전에 만들어 놓은 최소힙 문제 풀 때 썼던 코드에서 약간만 수정해서 풀기로 했습니다. 🙄

힙으로 바꾸니까 통과했습니다. 😘

 

파이썬이 더 쉽게 풀 수 있는 것을 알면서도. 자료구조를 구현하는 능력을 키우고자 js로 풀기로 마음 먹었는데 오늘 제 자신과의 약속을 깨버렸습니다.🤥

 

벌로 최소힙 10번 구현하고 자야겠습니다. 😓

 

 

class MinHeap {
  constructor() {
    this.heap = [];
  }

  empty() {
    if (this.heap.length == 0) {
      return true;
    }
    return false;
  }

  swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
    return;
  }


  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.heap[parentIndex].cost <= this.heap[currentIndex].cost) break;
      this.swap(this.heap, parentIndex, currentIndex)
      currentIndex = parentIndex;
    }
  }


  extractMin() {
    if (this.heap.length == 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min
  }

  sinkDown(index) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    const length = this.heap.length;
    let smallestIndex = index;

    if (leftIndex < length && this.heap[leftIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < length && this.heap[rightIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
      this.swap(this.heap, index, smallestIndex);
      this.sinkDown(smallestIndex)
    }
  }
}


const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n').map(v => v.split(' ').map(v => +v));
const [N, _] = input.shift();
const S = input.shift()[0];

let cost = new Array(N + 1).fill(Infinity);
let adj = Array.from(Array(N + 1), () => [])

input.forEach(x => {
  const [u, v, w] = x;
  adj[u].push([v, w]);
})

cost[S] = 0;

let heap = new MinHeap();
heap.insert({ node: S, cost: 0 });

while (!heap.empty()) {
  let now = heap.extractMin();
  for (let i = 0; i < adj[now.node].length; i++) {
    const [n, c] = adj[now.node][i];
    if (cost[n] > now.cost + c) {
      cost[n] = now.cost + c;
      heap.insert({ node: n, cost: cost[n] })
    }
  }
}
cost.shift();
cost.forEach((v, i) => {
  if (v === Infinity) {
    cost[i] = 'INF'
  }
})
console.log(cost.join('\n'));