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

혅·2025년 2월 6일

백준, 프로그래머스 -JavaScript-

목록 보기

194/215

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

내가 했던 풀이 방법

graph에 [연결된 node, cost] 형식으로 연결 리스트로 저장해준다.
minHeap(우선순위 큐)를 구현하고 Dijkstra를 우선순위 큐를 활용하여 start를 시작으로 모든 노드까지의 최단 거리(distance)를 반환하도록 구현한다.
출발점(1번 노드)와 v1, v2 지점을 출발점으로 했을 때의 최단 거리를 구해서 toStart, toV1, toV2에 저장한다.
특정한 지점을 건너는 최단 거리는 해당 거리를 경유해야 하므로 경우는 2가지가 존재한다. 1) 1->v1->v2->N 2) 1->v2->v1->N 두 값 중 최소 값을 answer에 저장한다.
answer가 Infinity일 경우 -1을 아닐 경우 answer를 출력한다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, E] = n.trim().split(' ').map(Number);
let [v1, v2] = input[input.length - 1].trim().split(' ').map(Number);

let graph = Array.from({ length: N + 1 }, () => []);
for (let i = 0; i < input.length - 1; i++) {
  let [a, b, c] = input[i].trim().split(' ').map(Number);
  graph[a].push([b, c]);
  graph[b].push([a, c]);
}

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

  enqueue(value) {
    this.heap.push(value);
    let current = this.heap.length - 1;
    let parent = Math.floor(current / 2);

    while (parent > 0 && this.heap[current][1] < this.heap[parent][1]) {
      [this.heap[current], this.heap[parent]] = [this.heap[parent], this.heap[current]];
      current = parent;
      parent = Math.floor(current / 2);
    }
  }

  dequeue() {
    if (this.heap.length === 1) return null;
    if (this.heap.length === 2) return this.heap.pop();

    let result = this.heap[1];
    this.heap[1] = this.heap.pop();
    let current = 1;

    while (true) {
      let left = 2 * current;
      let right = left + 1;
      let smallest = current;

      if (left < this.heap.length && this.heap[left][1] < this.heap[smallest][1]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right][1] < this.heap[smallest][1]) {
        smallest = right;
      }

      if (smallest === current) break;
      [this.heap[current], this.heap[smallest]] = [this.heap[smallest], this.heap[current]];
      current = smallest;
    }

    return result;
  }

  getSize() {
    return this.heap.length - 1;
  }
}

function Dijkstra(start) {
  let distance = Array.from({ length: N + 1 }, () => Infinity);
  let visited = Array.from({ length: N + 1 }, () => false);
  let pq = new MinHeap();
  pq.enqueue([start, 0]);
  distance[start] = 0;

  while (pq.getSize() > 0) {
    let [node, cost] = pq.dequeue();

    if (!visited[node]) {
      visited[node] = true;

      for (let i = 0; i < graph[node].length; i++) {
        let [nextNode, nextCost] = graph[node][i];

        if (distance[nextNode] > cost + nextCost) {
          distance[nextNode] = cost + nextCost;
          pq.enqueue([nextNode, nextCost + cost]);
        }
      }
    }
  }

  return distance;
}

let toStart = Dijkstra(1);
let toV1 = Dijkstra(v1);
let toV2 = Dijkstra(v2);

let answer = Math.min(toStart[v1] + toV1[v2] + toV2[N], toStart[v2] + toV2[v1] + toV1[N]);
console.log(answer === Infinity ? -1 : answer);