[JS] 백준 1504 - 특정한 최단 경로

해당 문제는 간선의 가중치가 0 이상이고, 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이기 때문에, 다익스트라 알고리즘을 사용하면 될 것 같았다. 단, 조건이 하나 붙게 되는데 주어진 두 정점을 반드시 거쳐야 하는 정점 번호가 주어진다. 

 

 

 

 

1번 노드로 시작했을 때 최단경로, v1 노드로 시작했을 때 최단 경로, v2로 시작했을 때 최단 경로를 각각 구해주면 된다. 

v1을 먼저 방문하는 경로와 v2를 먼저 방문하는 경로가 있을 수 있는데 둘 중 더 작은 값이 나오는 걸로 결과를 도출하면 된다.

 

 

코드

(function main() {
  const fs = require("fs");
  const isLocal = true;
  const filePath = isLocal ? "t.txt" : "/dev/stdin";
  const input = fs.readFileSync(filePath).toString().trim().split('\n');

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

    size() {
      return this.items.length
    }

    pop() {
      if (this.size() === 0) {
        return
      }

      const min = this.items[0]
      this.items[0] = this.items[this.size() - 1]
      this.items.pop()
      this.bubbleDown()

      return min
    }

    push(item) {
      this.items.push(item)
      this.bubbleUp()
    }

    swap(a, b) {
      [this.items[a], this.items[b]] = [this.items[b], this.items[a]]
    }

    bubbleUp() {
      let index = this.size() - 1

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

    bubbleDown() {
      let index = 0
      while (index * 2 + 1 < this.size()) {
        let leftChild = index * 2 + 1
        let rightChild = index * 2 + 2

        let smallerChild = rightChild < this.size() && this.items[rightChild][0] < this.items[leftChild][0] ? rightChild : leftChild

        if (this.items[index][0] < this.items[smallerChild][0]) {
          break
        }

        this.swap(index, smallerChild)
        index = smallerChild
      }
    }
  }

  const [N, E] = input[0].split(' ').map(Number)

  const graph = Array.from({ length: N + 1 }, () => [])
  const required = input[input.length - 1].split(' ').map(Number)
  console.log(required)

  for (let i = 1; i < input.length - 1; i++) {
    const [a, b, c] = input[i].split(' ').map(Number)
    graph[a].push([b, c])
    graph[b].push([a, c])
  }

  function dijkstra(start) {
    const dist = Array.from({ length: N + 1 }, () => Infinity)

    const pq = new MinHeap()
    pq.push([0, start])
    dist[start] = 0

    while (pq.size() > 0) {
      const [curDist, curNode] = pq.pop()
      if (curDist > dist[curNode]) {
        continue
      }

      for (let [adjNode, adjDist] of graph[curNode]) {
        const newDist = curDist + adjDist

        if (dist[adjNode] > newDist) {
          pq.push([newDist, adjNode])
          dist[adjNode] = newDist
        }
      }
    }

    return dist
  }

  const distFrom1 = dijkstra(1)
  const distFromV1 = dijkstra(required[0])
  const distFromV2 = dijkstra(required[1])

  const case1 = distFrom1[required[0]] + distFromV1[required[1]] + distFromV2[N]
  const case2 = distFrom1[required[1]] + distFromV2[required[0]] + distFromV1[N]

  const result = Math.min(case1, case2)

  console.log(result >= Infinity ? -1 : result)
})();