문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

---

예제

예제 입력 1

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

예제 출력 1

0
2
3
7
INF

---

해결

전형적인 다익스트라 알고리즘 문제로 보인다. 내가 참고한 글은 https://yabmoons.tistory.com/364 이다. 다른 글도 많지만 여기 블로그가 그림으로 잘 설명되있다.

위 글을 읽고 이해한 내용을 간략하게 설명해보고자 한다.

다익스트라는 방향과 가중치가 존재하는 그래프로 어느 한 노드에서 다른 노드로 갈 때 최단거리를 찾는 알고리즘이다. 다익스트라를 해결하기 위한 핵심은 그리디 알고리즘과 비슷하다고 느꼈다. 왜냐하면 현재의 노드에서 인접한 노드들이 여러개가 존재하는 상황에서 지금 당장 가야만 하는 노드는 최단거리의 노드라는 점이기 때문이다. 그렇기에 현재노드에서 갈 수 있는 노드의 조건은 다음과 같다.
1. 아직 최단거리를 찾지 못한 노드(= 아직 방문하지 못한 노드)
2. 갈 수 있는 노드들 중에서 가장 최단거리인 노드
위 와 같은 조건을 만족하는 노드를 찾아 그래프를 탐색하여 모든 노드까지의 최단거리를 구할 수 있다.

const distance = new Array(V + 1).fill(Infinity);
const visited = new Array(V + 1).fill(0);
const adjArr = Array.from({ length: V + 1 }, () => new Array());

for (let i = 0; i < E; i++) {
  const [from, to, weight] = input[i];
  adjArr[from].push([to, weight]);
}
distance[start] = 0;
visited[start] = 1;

let next = start;

<!--2번조건인 가장 최단거리인 노드를 찾아 반환한다.-->
const findNextV = () => {
  let min = Infinity;
  let minV = null;

  for (let i = 1; i <= V; i++) {
    if (!visited[i]) {
      if (distance[i] < min) {
        min = distance[i];
        minV = i;
      }
    }
  }

  if (!minV) return -1;
  else return minV;
};

while (1) {
  const cur = next;

  for (let i = 0; i < adjArr[cur].length; i++) {
    const [to, dis] = adjArr[cur][i];
    <!-- 1번 조건을 만족하는 노드들의 최단거리를 갱신해준다. -->
    if (!visited[to]) {
      if (distance[to] > distance[cur] + dis)
        distance[to] = distance[cur] + dis;
    }
  }

  const vaild = findNextV();
  if (vaild === -1) break;
  next = vaild;
  visited[next] = 1;
}

let answer = "";
for (let i = 1; i <= V; i++) {
  if (distance[i] === Infinity) answer += "INF\n";
  else answer += `${distance[i]}\n`;
}
console.log(answer);

위 코드를 작성하여 제출하면 통과는 할 수 있지만 시간복잡도 측면에서는 상당히 비효율적인 것을 확인했다. 그 이유는 다음과 같다.
1. 모든 노드를 탐색한다. O(N)
2. 각 노드마다 다음으로 갈 수 있는 노드를 찾기 위해 모든 노드를 탐색한다. O(N)

1번과 2번을 동시에 진행하기에 시간복잡도는 log(N^2)을 나타낸다. 노드가 100,000개 라면 100억 번의 탐색을 진행해야하기 때문이다. 이러한 비효율적인 시간복잡도를 해결하기 위해최소힙을 사용하여 다음 노드를 탐색하는 과정을 logN으로 줄여 시간복잡도를 O(NlogN)으로 만들 수 있다.

class MinHeap {
  constructor() {
    this.heap = [];
  }
  push(node, weight) {
    this.heap.push({ node, weight });
    if (this.heap.length === 1) return;
    let curIdx = this.heap.length - 1;
    let parentIdx = parseInt((curIdx - 1) / 2);
    while (
      curIdx > 0 &&
      this.heap[parentIdx].weight > this.heap[curIdx].weight
    ) {
      this.swap(curIdx, parentIdx);
      curIdx = parentIdx;
      parentIdx = parseInt((curIdx - 1) / 2);
    }
  }
  pop() {
    if (this.heap.length === 0) return -1;
    if (this.heap.length === 1) return this.heap.pop();
    const answer = this.heap[0];
    this.heap[0] = this.heap.pop();

    let pos = 0;

    while (1) {
      let cur = pos;
      let leftIdx = cur * 2 + 1;
      let rightIdx = cur * 2 + 2;
      if (leftIdx > this.heap.length - 1) break;

      if (this.heap[cur].weight > this.heap[leftIdx].weight) cur = leftIdx;
      if (
        rightIdx < this.heap.length &&
        this.heap[cur].weight > this.heap[rightIdx].weight
      )
        cur = rightIdx;

      if (cur === pos) break;
      this.swap(pos, cur);
      pos = cur;
    }

    return answer;
  }
  swap(a, b) {
    const tmp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = tmp;
  }
}

const heap = new MinHeap();
const visited = new Array(V + 1).fill(0);
const distance = new Array(V + 1).fill(Infinity);
const adjArr = Array.from({ length: V + 1 }, () => new Array());

for (let i = 0; i < E; i++) {
  const [from, to, dis] = input[i];
  adjArr[from].push({ to, dis });
}

distance[start] = 0;
heap.push(start, 0);

while (heap.heap.length) {
  const { node, weight } = heap.pop();
  visited[node] = 1;

  for (let i = 0; i < adjArr[node].length; i++) {
    const { to, dis } = adjArr[node][i];
    if (!visited[to]) {
      if (distance[to] > weight + dis) {
        distance[to] = weight + dis;
        heap.push(to, distance[to]);
      }
    }
  }
}
let answer = "";
for (let i = 1; i <= V; i++) {
  if (distance[i] === Infinity) answer += "INF\n";
  else answer += `${distance[i]}\n`;
}
console.log(answer);

첫번째 풀이는 2616ms, 두번째 풀이는 1112ms로 시간복잡도가 상당히 개선된 것을 확인할 수 있다.