백준 5719 거의 최단 경로

5719번: 거의 최단 경로

문제 설명

문제 핵심.

1. 구하고자 하는 "거의 최단 경로"란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 짧은 것을 말합니다.

2. 거의 최단 경로가 없는 경우 "-1"을 출력합니다.

 

풀이.

1. 주어진 S노드에서 출발 했을 때 각 노드까지의 최단 거리를 "다익스트라" 알고리즘을 통해 구해줍니다.

2. 도착 노드인 D노드로 이동하는데 포함하는 최단 거리 간선의 경우 방문 처리를 해줍니다.

3. 다익스트라 알고리즘에 방문하지 않은 간선의 경우만을 이동 가능한 경로로 생각하고 최단 거리(정답)을 구해 줍니다. 

 

우선 위와 같은 로직을 구현하기 위해서는 정상적인 단방향 그래프를 입력 받아주고, D -> S(역으로) 이동하며 최단 경로에 포함된 간선의 경우 방문처리를 해주어야 하기 때문에 역방향 그래프를 입력받아 줍니다.

const [U, V, P] = line.split(" ").map(Number);
graph[U].push([V, P]);
reverseGraph[V].push([U, P]);

방문 처리를 해주기위해 간선(2차 배열)방문 배열을 만들어 줍니다.

visit = Array.from({ length: N }, () => Array(N).fill(false));

그리고, 다익스트라 알고리즘에 사용될 minHeap또한 구현해 주었습니다.

 

이제 코드의 주석으로 나머지 설명을 대신합니다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 노드 개수, 간선 개수
let N, M;
// 출발, 도착
let S, D;
// 정방향 그래프
let graph = []; 
// 역방향 그래프 (D -> S(역으로) 탐색하며 최단 거리에 포함된 간선을 찾기위해)
let reverseGraph = []; 
// 최단 거리에 포함된 간선을 방문 처리해주기 위한 배열
let visit = [];
const INF = Infinity;

function MinHeap() {
  this.queue = [null];

  this.size = () => this.queue.length - 1;
  this.enqueue = (arr) => {
    this.queue.push(arr);
    let size = this.queue.length - 1;

    while (
      size > 1 &&
      this.queue[Math.floor(size / 2)][1] > this.queue[size][1]
    ) {
      const temp = this.queue[Math.floor(size / 2)];
      this.queue[Math.floor(size / 2)] = this.queue[size];
      this.queue[size] = temp;
      size = Math.floor(size / 2);
    }
  };

  this.dequeue = () => {
    if (this.queue.length === 2) return this.queue.pop();
    const removeItem = this.queue[1];
    this.queue[1] = this.queue.pop();
    let p = 1;
    let c = 2;

    while (this.queue.length > c) {
      if (
        c + 1 < this.queue.length &&
        this.queue[c + 1][1] < this.queue[c][1]
      ) {
        c = c + 1;
      }
      if (this.queue[p][1] < this.queue[c][1]) break;
      const temp = this.queue[p];
      this.queue[p] = this.queue[c];
      this.queue[c] = temp;
      p = c;
      c *= 2;
    }
    return removeItem;
  };
}

function dijkstra(start) {
  const distance = Array.from({ length: N }, () => INF);
  const minHeap = new MinHeap();
  minHeap.enqueue([start, 0]);
  distance[start] = 0;

  while (minHeap.size()) {
    const [now, dist] = minHeap.dequeue();

    graph[now].forEach(([n, cost]) => {
      const nDist = dist + cost;
      // 방문 처리된(최단 경로에 포함된)경우를 제외한 최단 거리 탐색
      if (nDist < distance[n] && !visit[now][n]) {
        distance[n] = nDist;
        minHeap.enqueue([n, nDist]);
      }
    });
  }

  return distance;
}

// bfs를 통해 D -> S(역으로) 탐색하며 최단 거리에 포함한 경로 방문 처리
function bfs(end, dist) {
  const queue = [end];
  let index = 0;

  while (queue.length > index) {
    const node = queue[index++];

    reverseGraph[node].forEach(([nNode, cost]) => {
      if (cost + dist[nNode] === dist[node] && !visit[nNode][node]) {
        queue.push(nNode);
        visit[nNode][node] = true;
      }
    });
  }
}

rl.on("line", function (line) {
  if (line === "0 0") {
    rl.close();
  } else if (N === undefined) {
    [N, M] = line.split(" ").map(Number);
    graph = Array.from({ length: N }, () => []);
    reverseGraph = Array.from({ length: N }, () => []);
    visit = Array.from({ length: N }, () => Array(N).fill(false));
  } else if (S === undefined) {
    [S, D] = line.split(" ").map(Number);
  } else {
    const [U, V, P] = line.split(" ").map(Number);
    graph[U].push([V, P]);
    reverseGraph[V].push([U, P]);

    if (--M === 0) {
      // solution
      const shortestDistance = dijkstra(S);
      bfs(D, shortestDistance);
      const almostShortestDistance = dijkstra(S);
      const result = almostShortestDistance[D];
      // 초기에 distance를 INF로 초기화해 주었기 때문에 
      // INF인 경우는 경로가 없다는 뜻이므로 -1 출력
      console.log(result === INF ? -1 : result);

      //초기화
      N = undefined;
      M = undefined;
      S = undefined;
      D = undefined;
    }
  }
});