[Algorithm] 최단경로 (백준 - 1753)

📋 문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

입출력 예

예제 입력	예제 출력
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6	0 2 3 7 INF

 

✏️ 풀이

다익스트라를 이용해서 풀었다. 최근 다익스트라 문제를 풀었던 적이 있는데 그때는 힙을 사용하지 않았었다. 이번에 문제를 풀면서 console.log를 최소화하거나, get, set의 최적화를 위해 위치정보를 저장하는 graph(아래 코드 상 dist)를 일반 객체가 아닌 Map을 이용하거나 해도 시간초과가 발생했고 결국 힙을 사용하게 되었다.

 

기본적인 로직은 다익스트라와 동일하다. 하나의 출발점에서 다른 모든 노드까지의 거리를 구할 수 있도록 배열(visited)을 사용해서 현재 방문 중인 노드에서 다른 노드로 이동할때 최소의 루트를 별도의 배열(costs)에서 최신화한다. 유일한 차이점이 다음으로 방문할 노드를 정하는 부분인데 힙을 사용하지 않을 때는 모든 노드를 탐색하면서 방문하지 않는 노드 중 가장 최소의 비용이 드는 노드로 골라서 이동하였다. 힙을 사용했을 때는 거리상으로 오름차순으로 정렬되기 때문에 가장 위 노드를 사용하면 된다. 이 부분에서 시간복잡도 n에서 LogN으로 줄며 시간초과 문제가 해결된 것 같다. 

 

⌨️ 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './testcase/1753.txt';

let inputs = fs.readFileSync(filePath).toString().trim().split('\n');
inputs = inputs.map(str => str.split(' ').map(Number));

class MinHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-1e9);
  }

  insert(value) {
    this.heap.push(value);
    this.upheap(this.heap.length - 1);
  }

  upheap(pos) {
    let temp = this.heap[pos];

    while (temp[1] < this.heap[parseInt(pos / 2)][1]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = temp;
  }

  get() {
    if (this.size() === 0) return 0;
    if (this.size() === 1) return this.heap.pop();
    const result = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return result;
  }

  downheap(pos, len) {
    let temp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child][1] > this.heap[child + 1][1]) child++;
      if (temp[1] <= this.heap[child][1]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = temp;
  }

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

const [V, E] = inputs[0];
const start = inputs[1][0];

const costs = new Array(V + 1).fill(Infinity);
const visited = new Array(V + 1).fill(0);

const dists = [...Array(V + 1)].map(_ => new Array());
for (let i = 2; i < inputs.length; i++) {
  const [u, v, w] = inputs[i];
  dists[u].push([v, w]);
}
costs[start] = 0;
const heap = new MinHeap();

heap.insert([start, 0]);

while (heap.size() > 0) {
  const [pos, dist] = heap.get();
  if (visited[pos]) continue;

  visited[pos] = true;
  for (let [next, dist] of dists[pos]) {
    if (costs[next] <= costs[pos] + dist) continue;
    costs[next] = dist + costs[pos];
    heap.insert([next, costs[next]]);
  }
}

const answer = [];
for (let i = 1; i <= V; i++) answer.push(costs[i] === Infinity ? 'INF' : costs[i]);
console.log(answer.join('\n'));