C++로 정확히 k개의 간선을 거쳐 출발점에서 목적지까지 가는 모든 경로 개수 구하기

이 튜토리얼에서는 그래프에서 정확히 k개의 간선을 사용하여 출발 정점(source)에서 목적지 정점(destination)까지 도달하는 모든 경로(walk)의 개수를 구하는 프로그램을 다룹니다.

그래프와 출발점, 목적지의 정보가 주어졌을 때, 우리의 목표는 간선을 정확히 k번 거쳐 출발점에서 목적지에 도착하는 모든 가능한 경로의 수를 찾는 것입니다.

알고리즘 접근 방식

가장 기본적인 방법은 재귀(recursion)를 이용하는 것입니다. 현재 정점에서 간선으로 연결된 인접 정점으로 한 칸씩 이동하면서, 남은 간선의 개수 k를 하나씩 줄여가며 탐색을 반복합니다.

재귀 호출의 종료 조건(기저 사례)은 다음과 같습니다.

• k == 0이고 현재 정점이 목적지와 같다면 → 경로 1개를 찾은 것이므로 1을 반환
• k == 1이고 현재 정점에서 목적지로 가는 간선이 존재하면 → 1을 반환
• k <= 0이라면 → 더 이상 진행할 수 없으므로 0을 반환

각 정점에서 인접한 모든 정점으로 이동하는 경우의 수를 재귀적으로 합산하면, 조건을 만족하는 전체 경로의 개수를 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
#define V 4
// 재귀를 이용한 경로 개수 계산
int countwalks(int graph[][V], int u, int v, int k){
    if (k == 0 && u == v)
        return 1;
    if (k == 1 && graph[u][v])
        return 1;
    if (k <= 0)
        return 0;
    int count = 0;
    // 인접한 노드로 이동
    for (int i = 0; i < V; i++)
        if (graph[u][i] == 1)
            count += countwalks(graph, i, v, k-1);
    return count;
}
int main(){
    int graph[V][V] = {
        {0, 1, 1, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    int u = 0, v = 3, k = 2;
    cout << countwalks(graph, u, v, k);
    return 0;
}

출력 결과

2

위 예제에서 정점 0에서 정점 3까지 정확히 2개의 간선을 거쳐 가는 경로는 0 → 1 → 3과 0 → 2 → 3, 총 2가지이므로 결과값으로 2가 출력됩니다.

시간 복잡도

이 재귀적 방법의 시간 복잡도는 O(V^k)입니다. 각 단계마다 최대 V개의 인접 정점으로 분기되기 때문입니다. 따라서 그래프의 크기가 크거나 k가 커질 경우 비효율적일 수 있는데, 이때는 동적 계획법(DP)이나 인접 행렬 거듭제곱(matrix exponentiation) 기법을 활용하면 O(V^3 log k) 시간 안에 더 효율적으로 문제를 해결할 수 있습니다.