[Algorithm] 다익스트라 알고리즘 — 최단 경로 찾기

문제 분석

---

프로그래머스 레벨 2의 배달 문제(12978)는 마을 개수 N, 두 마을 사이의 거리 정보 road, 배달 가능한 시간(거리) K를 인자로 받아, 1번 마을에 있는 음식점이 K이하 시간에 배달할 수 있는 마을의 개수를 반환해야 한다.

 

• 마을 개수 N : 1 ≤ N ≤ 50
• 거리 정보 : [[a, b, c], [...]]
  • a b : 두 마을의 번호
  • c : 두 마을의 거리(시간)
• 배달 가능한 시간 K : 1 ≤ K ≤ 500,000

 

이미지 출처 - 프로그래머스

위 마을 이미지를 기준으로 1번부터 5번 마을까지 최소 배달 시간을 [번호, 시간] 배열 형태로 나타내면 아래와 같다. 만약 배달 가능한 시간 K가 3이라면 1, 2, 4, 5번 마을이 모두 3시간 이하여서 정답은 4가 된다.

 

 

이처럼 1번 마을에서 다른 모든 마을까지 소요되는 최단 거리(시간)를 계산해야만 정답을 구할 수 있다. 1번 마을에서 1번 마을까지의 거리는 항상 0으로 취급한다. 이 문제는 다익스트라 알고리즘을 활용하면 해결할 수 있다.

 

다익스트라 알고리즘은 최단 경로를 계산할 때 사용하는 가장 대표적인 알고리즘 중 하나로 길찾기 등 현실 세계에서 자주 활용된다. 알고리즘의 동작 과정은 아래와 같다.

 

1. 출발 노드 설정 (일반적으로 1부터 시작)
2. 최단 거리 테이블 초기화
3. 방문하지 않은 (노드 중 거리가 가장 짧은) 노드 선택
4. 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산해서 최단 거리 테이블 갱신
5. 3~4번 과정 반복

 

💡 그리디 알고리즘은 매 선택에서 지역적으로 최적의 선택을 통해 전역적인 최적해를 구하는 방식이다.

 

다익스트라 알고리즘은 매 상황에서 거리가 가장 짧은(비용이 가장 적은) 노드를 선택하는 과정을 반복한다는 점에서 그리디 알고리즘으로 분류한다. 이미 계산한 최단 경로를 저장하고 재활용하는 점에 있어 다이나믹 프로그래밍과 유사한 면도 있다.

 

동작 방식 톺아보기

---

다익스트라 알고리즘은 거리 배열(Distance Array), 탐색 큐(Search Queue), 인접 리스트(Adjacency List) 이렇게 3가지를 기반으로 동작한다.

 

1. 거리 배열 : 각 노드까지의 최단 거리 정보. 시작시 모든 값은 ∞ 무한대로 초기화되며, 출발 노드의 거리는 0으로 설정한다. 이 배열은 알고리즘이 진행되면서 계속 업데이트 된다.
2. 탐색 큐 : 다음번 방문할 노드 목록. 일반적으로 거리가 짧은 노드를 효율적으로 검색하고 먼저 방문하기 위해 우선순위 큐로 구현한다. 탐색 큐의 초기값은 출발 노드로 설정한다.
3. 인접 리스트 : 각 노드에 인접해 있는 노드와 거리(가중치) 정보. 이 리스트를 통해 주어진 노드에서 이동할 수 있는 인접 노드를 빠르게 찾을 수 있다.

 

파라미터가 N=5, road=[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 일 때 거리 배열, 탐색 큐, 인접 리스트 및 노드 그래프는 아래 이미지처럼 구성된다.

 

N=5, road=[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]

먼저 시작 노드(N1)와 인접해 있는 노드를 살펴본다. 인접 리스트를 통해 N1은 N2, N4 노드와 연결되어 있는 걸 확인할 수 있다. N1에서 N2까지의 거리는 1이다. 1은 현재 거리 배열에 저장되어 있는 ∞ 무한대보다 작으므로 거리 배열을 업데이트한다. N4 노드까지의 거리 역시 저장되어 있는 거리 값보다 작으므로 업데이트한다.

 

거리 배열을 업데이트한 노드는 노드 번호와 해당 노드까지의 가중치(거리) 정보를 탐색 큐에 추가한다. N2, N4의 거리 배열을 업데이트 했으므로 [N2, D1], [N4, D2]가 큐에 추가된다.

 

• [N2, D1] : 출발 노드부터 N2 노드까지 거리는 1
• [N4, D2] : 출발 노드부터 N4 노드까지 거리는 2

 

현재 노드 : [N1, D0]

이제 탐색 큐에서 거리가 가장 짧은 노드를 살펴본다. N2 노드의 거리가 가장 짧으므로 탐색 큐에서 꺼낸다. N2는 N1, N3, N5와 인접해 있다. 각각 거리를 살펴본다.

 

• N1 : 이미 방문한 노드여서 Pass (거리 배열에 저장된 값과 비교했을 때 더 크다면 이미 방문한 노드로 간주)
• N3 : ∞ (거리 배열에 저장된 값) > 4 (출발노드 → N2 거리 1 + N2 → N3 거리 3)
• N5 : ∞ (거리 배열에 저장된 값) > 3 (출발노드 → N2 거리 1 + N2 → N5 거리 2)

 

N3, N5 까지의 거리가 배열에 저장된 거리 값보다 작으므로 거리 배열을 업데이트 하고 탐색 큐에 추가한다.

 

현재 노드 : [N2, D1]

다시 탐색 큐에서 거리가 가장 짧은 노드를 꺼낸다. 위와 동일하게 인접해 있는 노드의 거리를 확인한다. 하지만 최단 거리 배열을 모두 완성했으므로 큐에 있는 N4, N5, N3을 모두 꺼내서 확인해도 거리 배열에 있는 값이 더 작으므로 변경되는건 없다.

 

현재 노드 : [N4, D2]

현재 노드 : [N5, D3]

현재 노드 : [N5, D4]

출발 지점에서 모든 노드까지의 최단 거리 계산을 완료했다.

 

• 1번 노드까지의 최단 거리 : 0
• 2번 노드까지의 최단 거리 : 1
• 3번 노드까지의 최단 거리 : 4
• 4번 노드까지의 최단 거리 : 2
• 5번 노드까지의 최단 거리 : 3

 

우선순위 큐 vs 일반 큐

---

만약 배열을 이용해 큐를 구현했다면 노드 선택이 무작위로 이뤄져서 불필요한 노드 검토가 늘어나게 된다. 아래 이미지를 보면 항상 가중치가 가장 낮은 노드를 선택했을 때, 단 2번의 검토(큐에서 노드 2회 선택)만으로 모든 노드에 대한 최단 경로를 확인할 수 있다.

 

반면, 우측의 일반 큐 방식처럼 가중치를 고려하지 않고 비효율적인 순서로 노드를 선택한 경우 3번의 검토가 필요해진다. 그래프의 규모가 커질수록 이러한 비효율은 더욱 증가해서 전체 알고리즘 성능에 영향을 미칠 수 있다.

 

 

구현 방식에 따른 시간 복잡도

---

다익스트라 알고리즘은 탐색 큐를 어떤 자료구조로 구현했는지에 따라 성능이 크게 달라진다. E(Edge)는 간선 수, V(Vertex)는 노드 수라고 했을 때 시간 복잡도는 다음과 같다.

 

• 일반 큐로 구현한 경우 : 각 노드에 대해 최소 거리 값을 찾는 작업을 수행하므로 $O(V^{2})$
• 최소 힙(Min-Heap)으로 우선순위 큐를 구현한 경우 :
  • 우선순위 큐에서 최소 거리값을 갖는 노드 dequeue : $O(V \log V)$
    우선순위 큐에서 거리가 가장 짧은 노드를 꺼내는데 $O(\log V)$ 시간이 소요되고, 모든 노드에 대해 이 연산을 한 번씩 수행하므로 시간복잡도는 $O(V \log V)$ — V개의 dequeue 연산에 대한 총 합
  • 인접한 간선을 검토하면서 우선순위 큐에 enqueue : $O(E \log V)$
    우선순위 큐에 노드를 추가하는 작업은 각 간선마다 $O(\log V)$ 시간이 소요되고, 전체 간선에 대해 이 연산을 수행하므로 시간복잡도는 $O(E \log V)$ — E개의 enqueue 연산에 대한 총 합
  • 전체 시간 복잡도 : $O(E \log V)$
    일반적으로 간선 수 $E$가 노드 수 $V$보다 많거나 같아서 복잡도는 간선 연산에 의해 지배된다. 전체 시간 복잡도는 $O((E+V) \log V)$이지만, 간선 연산이 지배적이라는 가정하에 이를 $O(E \log V)$로 간소화하여 표현한다.

 

우선순위 큐는 일반 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 출력된다는 점이 다르다. 우선순위 큐는 크게 배열, 연결리스트, 힙 이렇게 세 가지 방법으로 구현할 수 있다. 그중 완전 이진 트리 구조를 갖는 힙으로 구현하면 추가/제거의 효율성이 크게 향상된다.

 

구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log n)	O(log n)

 

이진 트리는 각 부모 노드가 왼쪽/오른쪽 최대 2개의 자식 노드를 가질 수 있는 구조를 가리킨다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨을 완전히 채워진 상태로 유지해야 한다. 때문에 자식 노드를 추가할 땐 왼쪽부터 차례대로 채워야 한다. 아래 이미지 왼쪽에 있는 트리는 31번 노드의 자식을 오른쪽부터 채웠기 때문에 완전 이진 트리가 아니다.

 

 

힙은 크게 최대 힙(Max Heap), 최소 힙(Min Heap)으로 분류된다. 최대 힙은 부모 노드가 항상 자식 보다 크거나 같고, 최소 힙은 부모 노드가 항상 자식보다 작거나 같다. 다익스트라 알고리즘은 거리 값이 낮은 노드에 높은 우선순위를 부여하므로, 루트 노드가 가장 짧은 거리 값(우선순위가 높은)을 갖는 최소 힙을 사용하는 것이 적절하다.

 

 

코드로 구현

---

💡 최소 힙을 사용한 우선순위 큐 구현 방법은 링크 참고

 

인자로 받은 road 거리 정보에 대한 인접 리스트(그래프의 각 정점과 인접해 있는 정점들을 리스트로 표현한 자료구조)를 생성하는 createGraph 함수. 1부터 N(노드 개수)까지 번호를 매기므로 인덱스 0은 무시하기 위해 length 값에 1을 더해서 그래프를 생성한다. 즉, 그래프의 인덱스는 실질적으로 노드 번호를 가리키고 0번 노드는 존재하지 않으므로 0번 인덱스는 항상 [] 빈 배열이 된다.

const createGraph = (N, road) => {
  const graph = Array.from({ length: N + 1 }, () => []);

  road.forEach(([a, b, c]) => {
    graph[a].push({ node: b, dist: c });
    graph[b].push({ node: a, dist: c });
  });

  return graph; // [[], [{ node: 2, dist: 1 }, { node: 4, dist: 2 }], ...]
};

 

sort() 메서드로 구현한 우선순위 큐. 큐에 노드를 추가할 때마다 우선순위가 높은 노드가 가장 앞에 위치한다. 하지만 노드를 추가할 때마다 sort() 메서드로 정렬을 수행하기 때문에 $O(n \log n)$의 시간복잡도를 갖는다. 최소 힙(Heap)을 이용해서 구현하면 추가/삭제를 $O(\log n)$ 시간으로 처리할 수 있어서 더욱 효율적이다.

class PriorityQueue {
  constructor() {
    this.nodes = [];
  }

  enqueue(node, priority) {
    this.nodes.push({ node, priority });
    this.sort();
  }

  dequeue() {
    return this.nodes.shift();
  }

  sort() {
    this.nodes.sort((a, b) => a.priority - b.priority);
  }

  isEmpty() {
    return this.nodes.length === 0;
  }
}

 

자바스크립트는 64비트 IEEE 754 부동소수점을 사용하므로 $2^{53}-1$ 까지의 정수 값만 구별할 수 있다. 따라서 Number.Infinity 대신 안전한 정수 범위를 나타내는 상수인 Number.MAX_SAFE_INTEGER를 사용해서 최단 경로 목록의 초기값을 지정한다. 출발 지점부터 각 노드까지의 최단 경로를 나타내는 distances 배열의 인덱스는 노드 번호를 가리킨다. 예를들어 distances[2] 값이 3이라면 2번 노드까지의 최단 거리는 3이 된다.

 

또한, 우선순위 큐에서 꺼낸 노드의 거리 값이(출발 노드 → 해당 노드까지 거리) distances 배열에 저장된 값과 비교했을 때 더 크다면(distances[currentNode] < currentDist) 이미 방문한 노드로 간주해서 불필요한 연산을 건너뛸 수 있다.

const dijkstra = (N, graph, start) => {
  const distances = Array(N + 1).fill(Number.MAX_SAFE_INTEGER); // 각 노드의 최단 경로 초기화
  const queue = new PriorityQueue(); // 노드의 탐색 순서를 관리할 우선순위 큐 생성

  distances[start] = 0; // 1번 출발 노드의 최단 경로는 0으로 지정 [ Max, 0, Max, Max, Max, Max ]
  queue.enqueue(start, 0); // 출발 노드를 우선순위 큐에 추가

  while (!queue.isEmpty()) {
    const { node: currentNode, priority: currentDist } = queue.dequeue();
    if (distances[currentNode] < currentDist) continue; // 현재 노드의 최단 경로를 이미 계산했다면 건너뛰기

    graph[currentNode].forEach(({ node: nextNode, dist: nextDist }) => {
      const newDist = currentDist + nextDist;
      // 새로 계산한 거리가 기존에 알려진 거리보다 짧을 때만 업데이트
      if (newDist < distances[nextNode]) {
        distances[nextNode] = newDist;
        queue.enqueue(nextNode, newDist); // 최소 거리로 업데이트한 노드만 큐에 추가
      }
    });
  }
  return distances;
};

function solution(N, road, K) {
  const graph = createGraph(N, road); // road 거리 정보를 사용해서 인접리스트 생성
  const distances = dijkstra(N, graph, 1); // 시작 노드에서 각 노드까지의 최단 거리 계산
  return distances.filter(distance => distance <= K).length; // 최단 거리가 K 이하인 마을의 수 계산
}

solution(5, [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]], 3); // 4

const dijkstra = (N, graph, start) => {
  const distances = Array(N + 1).fill(Number.MAX_SAFE_INTEGER); // 각 노드의 최단 경로 초기화
  const queue = [{ node: start, dist: 0 }]; // 탐색할 노드 목록에 출발 노드(거리 값 0) 추가

  distances[start] = 0; // 1번 출발 노드의 최단 경로는 0으로 지정 [ Max, 0, Max, Max, Max, Max ]

  while (queue.length > 0) {
    const { node: currentNode, dist: currentDist } = queue.shift();
    if (distances[currentNode] < currentDist) continue; // 현재 노드의 최단 경로를 이미 계산했다면 건너뛰기

    graph[currentNode].forEach(({ node: nextNode, dist: nextDist }) => {
      const newDist = currentDist + nextDist;
      // 새로 계산한 거리가 기존에 알려진 거리보다 짧을 때만 업데이트
      if (newDist < distances[nextNode]) {
        distances[nextNode] = newDist;
        queue.push({ node: nextNode, dist: newDist }); // 최소 거리로 업데이트한 노드만 큐에 추가
      }
    });
  }
  return distances;
};

 

레퍼런스

---

• [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘
• [알고리즘] 다익스트라(Dijkstra) 알고리즘
• [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요