다익스트라

언제 쓰나

지점과 지점을 잇는 길마다 걸리는 시간이나 비용이 다르고, 한 출발지에서 다른 지점들까지 가장 적게 드는 비용을 구해야 할 때 씁니다.

• “1번 마을에서 K시간 안에 갈 수 있는 마을의 수”, “모든 서버에 신호가 닿는 데 걸리는 시간”처럼 출발지 하나에서 나머지 전부까지의 최단 거리를 묻습니다.
• 길마다 비용이 다릅니다. 모든 길의 비용이 같으면 지나는 길의 개수가 곧 거리이므로 BFS로 충분합니다.
• 비용이 모두 0 이상입니다. 음수 비용이 있는 길이 있으면 다익스트라의 전제가 깨져서 벨만-포드 같은 다른 알고리즘을 씁니다.

어떻게 동작하나

가까운 마을부터 거리를 확정한다

프로그래머스 「배달」은 마을 N개와 마을을 잇는 양방향 도로 목록 road가 주어질 때, 1번 마을에서 K시간 이하로 갈 수 있는 마을이 몇 개인지 구하는 문제입니다. 도로 [a, b, c]는 a번과 b번 마을을 잇고, 지나는 데 c시간이 걸립니다. 예제 1을 그림으로 옮기면 아래와 같고, 동그라미 안의 숫자가 마을 번호, 도로 위의 숫자가 걸리는 시간입니다.

가중치 그래프 · N = 5, K = 3

1번 마을에서 출발해 가까운 마을부터 차례로 거리를 정해 보겠습니다.

1. 1번 마을에서 바로 갈 수 있는 곳은 2번(1시간)과 4번(2시간)입니다. 두 마을의 라벨을 1과 2로 적습니다.
2. 라벨이 적힌 2번과 4번 가운데 2번이 1시간으로 더 가깝습니다. 2번으로 가는 다른 길이 있더라도 1번에서 출발하면 2번 아니면 4번으로 먼저 가야 하는데, 4번까지만 해도 이미 2시간이 걸립니다. 그러니 2번까지는 1시간보다 빨리 갈 수 없고, 2번의 거리를 1로 확정합니다.
3. 확정한 2번에서 이어지는 도로로 가 봅니다. 3번은 1 + 3 = 4시간, 5번은 1 + 2 = 3시간이라 라벨을 4와 3으로 적습니다.

여기까지 마친 그림은 이렇습니다.

가중치 그래프 · N = 5, K = 3

다음에는 아직 확정하지 않은 4번(2), 5번(3), 3번(4) 가운데 가장 가까운 4번을 2로 확정합니다. 4번에서 5번으로 가면 2 + 2 = 4시간인데, 5번에는 이미 3이 적혀 있으니 라벨을 그대로 둡니다. 같은 식으로 5번(3)과 3번(4)까지 확정하면, 3시간 이하로 갈 수 있는 마을은 1, 2, 4, 5번 네 곳입니다.

이렇게 확정하지 않은 마을 가운데 라벨이 가장 작은 마을을 하나씩 확정하고, 그 마을에서 나가는 도로로 이웃의 라벨을 줄여 나가는 방법을 다익스트라(Dijkstra) 알고리즘이라고 부릅니다. 1956년에 이 방법을 고안한 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 딴 것입니다. 그래프 용어로는 마을이 노드(node), 도로가 간선(edge), 도로를 지나는 시간이 간선의 가중치(weight)입니다. 3번 과정처럼 “여기를 거쳐 가면 더 빠른가”를 따져 라벨을 줄이는 일을 완화(relaxation)라고 합니다.

라벨이 가장 작은 마을은 왜 확정해도 되나

위 그림에서 4번의 라벨은 2입니다. 1번에서 4번으로 가는 길은 1번에서 바로 가는 도로 말고도 여러 가지가 있지만, 어느 길이든 확정한 마을(1번, 2번)을 벗어나는 순간 파란 마을 가운데 하나를 처음으로 지나야 합니다. 3번을 먼저 지나면 거기까지만 4시간, 5번을 먼저 지나면 3시간이 걸려 이미 2보다 깁니다. 그 뒤로 도로를 더 지나면 시간이 늘어나기만 하니, 4번까지 2시간보다 빨리 가는 길은 없습니다.

이 논리는 “도로를 더 지나면 시간이 줄지 않는다”는 전제, 즉 가중치가 0 이상이라는 조건에 기댑니다. 음수 가중치가 있으면 멀리 돌아가는 길이 나중에 더 짧아질 수 있어서, 먼저 확정한 거리가 틀릴 수 있습니다.

코드에서는 dist와 pq를 쓴다

• dist: 마을마다 지금 알고 있는 가장 짧은 거리입니다. 그림의 라벨과 같고, 처음에는 출발지만 0이고 나머지는 Infinity입니다.
• pq: 라벨이 적힌 마을들을 [거리, 마을] 쌍으로 담아 두고, 거리가 가장 작은 쌍을 먼저 꺼내는 우선순위 큐입니다. “확정하지 않은 마을 가운데 라벨이 가장 작은 마을”을 매번 전부 훑지 않고 O(log n)에 꺼내려고 씁니다.

한 번 반복할 때 하는 일은 두 가지입니다.

1. 확정: pq에서 거리가 가장 작은 [time, village]를 꺼냅니다. time이 dist[village]보다 크면 village가 이미 더 짧은 거리로 확정된 뒤 남아 있던 옛 후보라서 버리고, 아니면 village까지의 거리를 time으로 확정합니다.
2. 완화: village에서 이어지는 도로 [neighbor, roadTime]마다, village를 거쳐 neighbor에 닿는 시간 arrival = time + roadTime을 계산합니다. arrival이 dist[neighbor]보다 작으면 dist[neighbor]를 arrival로 줄이고 pq에 [arrival, neighbor]를 넣습니다.

pq가 빌 때까지 반복하면 dist의 모든 값이 확정됩니다. 이 예제에서는 옛 후보를 버리는 경우가 생기지 않지만, 같은 마을의 라벨이 두 번 줄어드는 그래프에서는 먼저 넣은 큰 후보가 pq에 남아 있다가 나중에 꺼내집니다.

직접 따라가 보기

아래에서 “다음”을 누르면 노란 마을이 방금 확정한 마을이고, 그 마을에서 나가는 도로가 하나씩 노랗게 칠해지며 이웃의 라벨이 줄어듭니다. 3~4번째 단계에서 2번과 4번의 라벨이 ∞에서 1과 2로 줄고, 9번째 단계에서는 4번에서 5번으로 가는 도로가 빨간 점선이 됩니다. 2 + 2 = 4가 5번에 이미 적힌 3보다 크니 라벨이 그대로이고, 계산한 4는 라벨 옆에 취소선으로 남습니다. 11번째 단계에서 5번을 거쳐 3번으로 가는 길도 4시간이라 3번의 라벨 4보다 작지 않습니다. 마지막 단계에서 3시간 이하인 1, 2, 4, 5번이 청록으로 바뀌고 결과가 예제 출력과 같은 4가 됩니다.

처음부터 이전 자동 재생 다음

단계 1 / 13

가중치 그래프 · N = 5, K = 3

변수

dist

[, 0, ∞, ∞, ∞, ∞]1~5번 마을

pq

[]

result

–

출발지 1번 마을의 거리만 0이고 나머지는 모두 ∞입니다. pq에 [0, 1]을 넣고 시작합니다. "다음"을 눌러 보세요

• 지금 확정해 이웃을 보는 마을
• 거리 후보가 있는 마을 · 지금까지의 최단 경로
• 거리를 확정한 마을
• 3시간 안에 닿는 마을

대표 문제 풀이

아래는 참고 풀이입니다. JavaScript에는 우선순위 큐가 없어서 MinHeap을 직접 둡니다. 힙 항목의 MaxHeap에서 비교 방향을 뒤집고, [거리, 마을] 쌍의 거리([0])끼리 비교하도록 바꾼 것입니다. solution의 ①②가 위의 두 규칙이고, 변수 이름은 시각화의 변수 칸과 같습니다.

class MinHeap {
  constructor() {
    // 0번 칸은 비워 두고 1번 칸부터 쓴다
    this.heap = [null];
  }

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

  /**
   * @param {[number, number]} item [거리 후보, 마을 번호]. 거리(item[0])가 작을수록 먼저 나온다
   */
  push(item) {
    const heap = this.heap;
    heap.push(item);
    let i = heap.length - 1;
    while (i > 1) {
      const parent = Math.floor(i / 2);
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }

  /**
   * @returns {[number, number]} 거리가 가장 작은 [거리 후보, 마을 번호]
   */
  pop() {
    const heap = this.heap;
    const top = heap[1];
    const last = heap.pop();
    if (heap.length > 1) {
      heap[1] = last;
      let i = 1;
      while (i * 2 < heap.length) {
        const left = i * 2;
        const right = i * 2 + 1;
        let smaller = left;
        if (right < heap.length && heap[right][0] < heap[left][0]) smaller = right;
        if (heap[i][0] <= heap[smaller][0]) break;
        [heap[i], heap[smaller]] = [heap[smaller], heap[i]];
        i = smaller;
      }
    }
    return top;
  }
}

function solution(N, road, K) {
  // graph[마을]: 그 마을에서 바로 갈 수 있는 [이웃 마을, 도로를 지나는 시간] 목록.
  // 도로는 양방향이라 양쪽 마을에 모두 넣는다
  const graph = Array.from({ length: N + 1 }, () => []);
  for (const [villageA, villageB, roadTime] of road) {
    graph[villageA].push([villageB, roadTime]);
    graph[villageB].push([villageA, roadTime]);
  }

  // dist[마을]: 1번 마을에서 그 마을까지 지금 알고 있는 가장 짧은 시간
  const dist = Array(N + 1).fill(Infinity);
  dist[1] = 0;
  // pq에는 [1번 마을에서 그 마을까지의 거리 후보, 마을 번호] 쌍이 들어간다.
  // 거리([0])가 가장 작은 쌍이 먼저 나오고, 같은 마을이 더 큰 거리로 한 번 더 들어 있을 수 있다
  const pq = new MinHeap();
  pq.push([0, 1]); // 출발지 1번 마을, 거리 0

  while (pq.size > 0) {
    // ① 거리가 가장 작은 마을을 꺼내 확정한다. 이미 더 짧게 확정된 옛 후보면 버린다
    const [time, village] = pq.pop();
    if (time > dist[village]) continue;

    // ② 이어진 마을로 가 보고, 더 짧으면 거리를 줄이고 pq에 넣는다
    for (const [neighbor, roadTime] of graph[village]) {
      const arrival = time + roadTime; // village를 거쳐 neighbor에 닿는 시간
      if (arrival < dist[neighbor]) {
        dist[neighbor] = arrival;
        pq.push([arrival, neighbor]);
      }
    }
  }

  return dist.filter((shortest) => shortest <= K).length;
}

dist는 마을 번호를 그대로 칸 번호로 쓰려고 N + 1칸으로 만들었습니다. 쓰지 않는 0번 칸은 Infinity로 남아 있어서, 마지막 filter에서 K 이하인 칸을 셀 때 끼어들지 않습니다.

마을 수를 V, 도로 수를 E라고 하면, 도로 하나를 따라 완화가 성공할 때마다 pq에 한 번 넣으니 pq에 들어가는 쌍은 E개 남짓이고, 넣고 꺼낼 때마다 O(log V) 정도가 듭니다. 그래서 전체 시간은 O((V + E) log V)이고, 공간은 인접 목록과 pq를 합친 O(V + E)입니다.