C++ 코딩테스트 강좌, 다익스트라

다익스트라 알고리즘(Dijkstra’s Algorithm)은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 데 매우 유용한 알고리즘입니다. 특히 가중치가 있는 그래프에서 최단 경로를 구하는 데 사용됩니다. 본 강좌에서는 다익스트라 알고리즘의 원리를 이해하고, C++을 사용하여 그 구현 방법을 배워보겠습니다.

문제 설명

주어진 N개의 도시와 M개의 도로가 있을 때, 한 도시에서 다른 도시로 가는 최소 비용을 구하시오. 각 도시는 정점으로 표현되고 도로는 그래프에서 간선으로 표현됩니다.

도시와 도로에 대한 정보는 다음과 같습니다:

  • 도시의 수: N (1 ≤ N ≤ 100,000)
  • 도로의 수: M (1 ≤ M ≤ 200,000)
  • 도로 정보: A, B, C (도시 A와 도시 B를 연결하는 도로의 가중치가 C)

예를 들어, 5개의 도시와 6개의 도로가 있는 그래프가 주어진다면, 다음과 같은 형태로 입력됩니다:

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

입력 형식

1번째 줄: N M
2번째 줄부터 M번째 줄: A B C (각 도로에 대한 정보)

출력 형식

각 도시(1~N)에 대한 최소 비용을 출력한다. 
불가능한 경우 -1을 출력한다.

예제 입력

5 7
1 2 2
1 3 3
2 3 1
2 4 4
3 4 2
3 5 5
4 5 1

예제 출력

1
2
3
3
4

알고리즘 설명

다익스트라 알고리즘은 한 정점에서 출발하여 다른 정점까지의 최단 경로를 찾기 위해 그리디 방식으로 작동합니다. 기본적인 구상은 다음과 같습니다:

  1. 모든 정점까지의 초기 거리를 무한대로 설정하고, 시작 정점의 거리는 0으로 설정합니다.
  2. 가장 짧은 거리를 가진 정점을 선택하고, 그 정점에 인접한 모든 정점의 거리를 업데이트합니다.
  3. 모든 정점에 대한 거리가 업데이트될 때까지 이 과정을 반복합니다.

구현 단계

  1. 그래프 생성: 인접 리스트를 사용하여 그래프를 표현합니다.
  2. 우선순위 큐 활용: 가장 짧은 경로를 찾기 위해 우선순위 큐(힙)를 사용합니다.
  3. 거리 배열 초기화: 각 정점에 대한 거리를 초기화합니다.
  4. 최단 경로 계산: 최소 거리 갱신 과정을 반복합니다.

C++ 코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

vector<pair<int, int>> graph[100001];
vector<int> dist;

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentDist > dist[currentNode]) continue;

        for (auto edge : graph[currentNode]) {
            int next = edge.first;
            int weight = edge.second;

            if (dist[currentNode] + weight < dist[next]) {
                dist[next] = dist[currentNode] + weight;
                pq.push(make_pair(dist[next], next));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    dist.resize(N + 1, numeric_limits<int>::max());

    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        graph[A].push_back(make_pair(B, C));
        graph[B].push_back(make_pair(A, C)); // 무향 그래프일 경우
    }

    dijkstra(1); // 1번 도시에서 시작

    for (int i = 1; i <= N; i++) {
        if (dist[i] == numeric_limits<int>::max()) {
            cout << -1 << &endl
        } else {
            cout << dist[i] << &endl
        }
    }

    return 0;
}

코드 설명

위의 코드에서는 다음과 같은 방식으로 다익스트라 알고리즘을 구현합니다:

  • 인접 리스트 생성: 주어진 도시와 도로 정보를 읽고, 그래프를 인접 리스트 형태로 표현합니다.
  • 우선순위 큐: 최소 거리를 찾기 위해 우선순위 큐를 사용하여 가장 짧은 거리를 계속해서 추출합니다.
  • 거리 갱신: 현재 정점에서 인접한 정점으로 이동할 때 새로운 거리가 더 짧으면 거리를 갱신합니다.
  • 최종 결과 출력: 각 도시까지의 최단 거리를 출력합니다. 도달할 수 없는 도시의 경우 -1을 출력합니다.

복습 및 마무리

이번 강좌를 통해 다익스트라 알고리즘의 작동 원리를 이해하고, C++로 구현하는 방법을 배웠습니다. 알고리즘과 자료구조는 코딩 테스트에서 매우 중요한 주제이며, 다익스트라 알고리즘은 특히 그래프 관련 문제에서 많이 활용됩니다. 추가적으로 BFS, DFS와 같은 그래프 탐색 알고리즘도 연습해보시기 바랍니다.

다익스트라 알고리즘을 심화 학습하기 위해서는 다양한 문제를 풀어보고, 다른 알고리즘과 비교해보는 것이 도움이 됩니다. 다음 번에는 벨만-포드 알고리즘이나 플로이드-워셜 알고리즘에 대해서도 알아보도록 하겠습니다. 감사합니다!