백준 node.js 1238번 파티 JavaScript JS 다익스트라

1238번: 파티

1. 다익스트라 알고리즘을 이용하여 문제를 풀었습니다.
2. 다익스트라 알고리즘은 노드와의 가중치가 다를 경우, 노드와 노드 사이의 최단 거리를 찾는 알고리즘 입니다.
3. 또한 가중치의 값은 양수이어야 합니다. 음수일 경우 다익스트라가 아닌 밸만 포드 알고리즘을 사용해야 합니다. 그렇지 않으면 싸이클에 빠집니다.
4. 이번 문제는 다음과 같이 풀었습니다
   1. X마을로 올 수 있는 최단 거리를 찾는다
   2. X마을에서 갈 수 있는 최단 거리를 찾는다
   3. 그 둘을 더한 값의 최댓값을 구한다.
5. 코드는 다음과 같습니다
   1. 다익스트라 알고리즘을 사용하기 위한 우선순위 큐 (최소 힙)을 구현합니다.
   2. 우선순위 큐를 이용하여 최단 거리를 찾습니다.

문제 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
//[도로의 시작점, 끝점, 소요시간]
//N번 마을에는 N학생이 살고있다.
//각 마을에서 X마을 까지의 최단거리를 구한다
//X마을에서 각 마을까지의 최단거리를 구한다.
const [N,M,X] = input[0].split(" ").map(Number)

//X마을로 올 수 있는 길
const nodes = Array.from({length:N+1},()=>[])
//X마을에서 갈 수 있는 길
const reverseNodes = Array.from({length:N+1},()=>[])

for(let i=1; i<=M; i++){
  const [str,end,time] = input[i].split(" ").map(Number)
  nodes[str].push([str,end,time])
  reverseNodes[end].push([end,str,time])
}

//최소 힙 구현
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].time > value.time){
      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();
    if(this.heap.length === 0) return null;
    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[currentIndex].time > this.heap[leftIndex].time )||
          (this.heap[rightIndex] && this.heap[currentIndex].time > this.heap[rightIndex].time)){
            if(this.heap[rightIndex] && this.heap[currentIndex].time > this.heap[rightIndex].time){
              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;
  }
}

//최소힙을 이용한 다익스트라 구현(최단 거리 찾기)
function find(arr){
  const queue = new minHeap();
  for(let [cur, next , time] of arr[X]){
    queue.push({cur, next, time})
  }

  const returnArray = Array(N+1).fill(Infinity)
  returnArray[X] = 0;

  while(queue.heap.length > 0){
  const {cur, next, time} = queue.pop()
    if(returnArray[next] > returnArray[cur] + time){
      returnArray[next] = returnArray[cur] + time
      for(let [ _ , next2,time2] of arr[next]){
        queue.push({cur : next, next : next2, time : time2})
      }
    }
  }

  return returnArray
}

const arr1 = find(nodes)
const arr2 = find(reverseNodes)

//최댓값 찾기
let answer = 0;
arr1.forEach((v,i) => {
  if(v+arr2[i] !== Infinity && answer < v+arr2[i]){
    answer = v+arr2[i]
  } 
})
console.log(answer)