C++ 코딩테스트 강좌, 경로 찾기

이 강좌에서는 C++를 사용하여 그래프에서 경로를 찾는 알고리즘을 구현합니다.
특히 BFS(너비 우선 탐색)를 이용하여 최단 경로를 찾는 방법을 다루고자 합니다.
이 과정에서 실제 코딩 테스트에서 자주 출제되는 문제를 풀이하며,
알고리즘 이론과 구현을 자세히 설명하겠습니다.

문제 설명

주어진 그래프에서 두 지점 사이의 최단 경로를 찾는 문제를 해결해야 합니다.
그래프는 노드와 에지로 구성되며, 각 노드는 서로 연결되어 있습니다.
일반적으로 이 문제는 다음과 같은 형식으로 주어집니다:

첫 번째 줄은 노드 수(정점)와 에지 수(간선)의 수를 나타내며,
두 번째 줄부터는 각 에지의 연결 정보를 나타냅니다.
마지막 줄은 시작 노드와 도착 노드를 의미합니다.

알고리즘 이론

그래프에서의 경로 찾기는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 두 가지 방법으로 수행할 수 있습니다.
본 강좌에서는 BFS를 사용하여 최단 경로를 찾는 방법에 중점을 두겠습니다.
BFS는 동작 방식이 직관적이며, 큐를 사용하여 모든 인접한 노드를 탐색하는 방식으로 진행됩니다.

BFS의 동작 원리

BFS의 기본 동작 원리는 다음과 같습니다:

시작 노드를 큐에 추가하고 방문 처리합니다.
큐에서 노드를 하나 꺼내 그 노드의 인접 노드를 모두 탐색합니다.
탐색한 인접 노드 중 방문하지 않은 노드를 큐에 추가하고 방문 처리합니다.
큐가 빌 때까지 2번과 3번 과정을 반복합니다.

BFS는 최단 경로를 보장하는 이유는 모든 노드를 같은 레벨에서 처리하기 때문입니다.
이렇게 레벨을 기준으로 탐색하기 때문에 최단 경로가 보장됩니다.

문제 해결 과정

이제 문제를 해결하기 위해 필요할 알고리즘을 구현하겠습니다.
아래는 문제 해결을 위한 C++ 코드입니다.


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int bfs(vector>& graph, int start, int end) {
    queue q;
    vector visited(graph.size(), false);
    vector distance(graph.size(), -1);
    
    q.push(start);
    visited[start] = true;
    distance[start] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
                
                if (neighbor == end) {
                    return distance[neighbor];
                }
            }
        }
    }
    return -1; // 경로가 없는 경우 
}

int main() {
    int n, m;
    cin >> n >> m;
    vector> graph(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // undirected graph
    }

    int start, end;
    cin >> start >> end;

    int result = bfs(graph, start, end);
    cout << result << endl;

    return 0;
}

코드 설명

위 코드는 그래프의 노드 수와 에지 수를 입력받고,
각 에지의 정보를 통해 그래프를 구축한 후 BFS를 이용하여
시작 노드와 종료 노드 사이의 최단 경로를 찾는 예제입니다.

먼저 필요한 헤더 파일을 포함하고, using namespace std;를 선언합니다.
bfs 함수는 그래프, 시작 노드, 종료 노드를 파라미터로 받습니다.
큐를 선언하고, 방문 여부를 나타내는 visited 벡터를 초기화합니다.
큐에 시작 노드를 추가하고 방문 처리합니다.
큐가 비어있지 않을 때까지 반복하면서 노드를 꺼내고 인접 노드를 탐색합니다.
방문하지 않은 인접 노드를 큐에 추가하고 거리 정보를 업데이트합니다.
종료 노드에 도달하면 해당 거리를 반환합니다.
거리 정보는 -1로 초기화됩니다; 경로가 없으면 -1을 반환합니다.

결과 및 분석

위 코드를 컴파일하고 입력 예시를 통해 실행하면,
시작 노드와 종료 노드 간의 최단 경로가 출력됩니다.
BFS는 모든 인접 노드를 탐색하므로, 최단 경로를 보장합니다.
그래프의 크기가 커질수록 탐색 시간이 비례하여 증가하지만,
BFS는 대부분의 그래프 문제에 적합한 알고리즘입니다.

복잡도 분석

BFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 노드의 수,
E는 에지의 수입니다. 메모리 복잡도 또한 O(V)입니다.
이 복잡도는 그래프의 구조에 따라 달라질 수 있습니다.
나쁜 경우(예: 완전 그래프)에는 E가 V^2가 될 수 있습니다.

마무리

이번 강좌에서는 C++를 사용하여 그래프에서 최단 경로를 찾는 문제를
BFS 알고리즘을 통해 해결했습니다. BFS의 이해와 그 구현은
코딩 테스트에서 중요한 부분이므로 충분히 연습하시길 바랍니다.
향후 더 다양한 문제를 통해 실력을 쌓아 나가시기를 바랍니다.