C++ 코딩테스트 강좌, 최단 경로 구하기

1. 문제 정의

최단 경로 구하기 문제는 주어진 그래프에서 두 정점 사이의 최소 거리를 찾는 문제입니다. 그래프는 노드(정점)와 이들을 연결하는 간선(엣지)으로 구성되며, 각 간선은 거리 또는 가중치로 표현됩니다.

예를 들어, 다음과 같은 그래프가 있다고 가정합시다. 여기서 A, B, C, D는 노드이며, 간선은 다음과 같은 가중치를 가집니다:

    A --1-- B
    |      /|
    4     2 |
    |  /      |
    C --3-- D

문제는 두 노드 A와 D 간의 최단 경로를 구하는 것입니다.

2. 알고리즘 선택

최단 경로 구하기 문제를 해결하기 위해 일반적으로 사용하는 알고리즘은 다익스트라(Dijkstra) 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘이 있습니다.

이 문제에서는 다익스트라 알고리즘을 사용하겠습니다. 다익스트라 알고리즘은 가중치가 음수가 아닌 그래프에서 최단 경로를 찾는 데 적합합니다.

2.1 다익스트라 알고리즘 설명

다익스트라 알고리즘은 다음과 같은 단계로 작동합니다:

  1. 시작 노드를 설정하고, 그 노드에 대한 최단 거리를 0으로 초기화합니다.
  2. 모든 다른 노드의 최단 거리를 무한대로 초기화합니다.
  3. 방문하지 않은 노드 중 가장 최단 거리 값이 낮은 노드를 선택합니다.
  4. 이 노드를 현재 노드로 설정하고, 이 노드를 통해 접근할 수 있는 모든 인접 노드의 최단 거리 값을 업데이트합니다.
  5. 모든 노드를 방문할 때까지 3-4 단계를 반복합니다.

3. C++ 구현

이제 C++로 다익스트라 알고리즘을 구현해 보겠습니다. 다음은 위에서 설명한 그래프의 최단 경로를 찾는 코드입니다:

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // numeric_limits를 위해
using namespace std;

// 그래프 구조체 정의
struct Edge {
    int destination;
    int weight;
};

// 다익스트라 알고리즘 구현
vector dijkstra(int start, const vector>& graph) {
    int n = graph.size();
    vector distance(n, numeric_limits::max());
    distance[start] = 0;
    
    priority_queue, vector>, greater>> minHeap;
    minHeap.push({0, start});

    while (!minHeap.empty()) {
        int currentDistance = minHeap.top().first;
        int currentNode = minHeap.top().second;
        minHeap.pop();

        // 현재 노드의 거리 값이 더 크면 무시
        if (currentDistance > distance[currentNode]) continue;

        // 인접 노드 탐색
        for (const Edge& edge : graph[currentNode]) {
            int newDistance = currentDistance + edge.weight;
            if (newDistance < distance[edge.destination]) {
                distance[edge.destination] = newDistance;
                minHeap.push({newDistance, edge.destination});
            }
        }
    }

    return distance;
}

int main() {
    // 그래프 초기화
    int n = 4; // 노드 개수
    vector> graph(n);
    
    // 간선 추가 (0-based index)
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
    graph[2].push_back({3, 3});
    
    int startNode = 0; // A
    vector shortestPaths = dijkstra(startNode, graph);

    // 결과 출력
    cout << "최단 경로:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "A에서 " << char('A' + i) << "까지의 최단 경로: ";
        if (shortestPaths[i] == numeric_limits::max()) {
            cout << "도달 불가능" << endl;
        } else {
            cout << shortestPaths[i] << endl;
        }
    }

    return 0;
}

4. 코드 설명

4.1 그래프 구조 설정

먼저, 간선 구조체를 정의하여 각 노드와 가중치 정보를 포함한 그래프를 설정합니다. vector<vector<Edge>>를 사용하여 그래프를 표현합니다.

4.2 다익스트라 구현

다익스트라 알고리즘을 위한 함수 dijkstra를 작성했습니다. 시작 노드에서부터 각 노드까지의 최단 거리를 계산하여 distance 벡터에 저장합니다. priority_queue를 사용하여 현재까지의 최단 경로를 효율적으로 관리합니다.

4.3 메인 함수

main 함수에서 그래프를 초기화하고, 다익스트라 함수를 호출하여 최단 경로를 구한 뒤, 결과를 출력합니다.

5. 복잡도 분석

다익스트라 알고리즘의 시간 복잡도는 사용된 자료 구조에 따라 달라집니다. 일반적으로 힙을 사용할 경우 O(E log V)로 나타내며, 여기서 E는 간선의 수, V는 노드의 수입니다.

6. 참고 자료

덧글: 이 코드는 샘플 그래프에 대해 작동하며, 실제 문제에 맞게 그래프를 수정해야 합니다. 유사한 형태의 문제를 풀기 위해 다익스트라 알고리즘의 변형이나 다른 접근법을 고려할 수 있습니다.

7. 결론

이번 글에서는 C++을 이용한 다익스트라 알고리즘을 통해 주어진 그래프에서 최단 경로를 구하는 방법을 배웠습니다. 알고리즘의 기본 개념, C++ 구현 방법과 예제를 통해 이해를 심화시킬 수 있었습니다. 실제 코딩 테스트에서는 이러한 알고리즘을 문제 해결에 응용하는 것이 중요합니다. 지속적으로 다양한 문제를 해결하며 경험을 쌓아 나가시길 바랍니다.