방향 그래프(directed graph)가 주어져 있습니다. 여기에 두 정점 u와 v가 추가로 주어지며, u는 시작 정점, v는 끝 정점입니다. 이때 풀어야 할 과제는 정점 u에서 v까지 정확히 k개의 간선을 거쳐 가는 워크(walk)의 개수를 찾는 것입니다. k의 값 역시 알고리즘의 입력으로 함께 제공됩니다.
이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심은 행(row)에는 u의 값을, 열(column)에는 v의 값을 배치하고, 깊이(depth) 차원으로 시작점부터 끝점까지 사용한 간선의 개수를 추적하는 3차원 테이블을 만드는 것입니다.
핵심 아이디어
count[i][j][e]는 정점 i에서 정점 j까지 정확히 e개의 간선을 사용하는 워크의 개수를 의미합니다.
- e = 0인 경우: 간선 없이 제자리에 머무는 경우 하나뿐이므로, i = j일 때만 1입니다.
- e = 1인 경우: i에서 j로 향하는 간선이 직접 존재하면 1입니다.
- e > 1인 경우: i의 인접 정점 a를 한 단계 거친 뒤, a에서 j까지 e−1개의 간선으로 가는 경우의 수를 모두 더합니다. 즉,
count[i][j][e] = Σ count[a][j][e−1](단, a는 i와 인접한 정점).
입력과 출력
그래프는 인접 행렬(adjacency matrix) 형태로 주어집니다. 아래 예제에서 목적지 정점은 3이고 K = 2입니다.
입력: 그래프의 인접 행렬: 목적지 정점은 3, K = 2 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 출력: 정점 0에서 3까지 간선 2개로 갈 수 있는 워크는 2개입니다.
알고리즘
numberOfWalks(u, v, k)
입력: 시작 정점 u, 끝 정점 v, 간선의 개수 k
출력: k개의 간선으로 만들 수 있는 워크의 개수
Begin
define 3D array count of order (n x n x k+1) // n은 정점의 개수
for edge in range 0 to k, do
for i in range 0 to n-1, do
for j in range 0 to n-1, do
count[i, j, edge] := 0
if edge = 0 and i = j, then
count[i, j, edge] := 1
if edge = 1 and (i, j) is connected, then
count[i, j, edge] := 1
if edge > 1, then
for a in range 0 to n, and adjacent with i do
count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1]
done
done
done
done
return count[u, v, k]
End
C++ 예제 코드
#include <iostream>
#define NODE 7
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
int numberOfWalks(int u, int v, int k) {
int count[NODE][NODE][k+1];
for (int edge = 0; edge <= k; edge++) { // 간선 수 0..k에 대해 반복
for (int i = 0; i < NODE; i++) {
for (int j = 0; j < NODE; j++) {
count[i][j][edge] = 0; // 초기값은 모두 0
if (edge == 0 && i == j) // edge가 0이고 i와 j가 같으면 워크는 1개
count[i][j][edge] = 1;
if (edge == 1 && graph[i][j]) // edge가 1이고 i→j 간선이 있으면 워크는 1개
count[i][j][edge] = 1;
if (edge > 1) { // 간선이 2개 이상인 경우
for (int a = 0; a < NODE; a++) // 출발 정점 i의 인접 정점 확인
if (graph[i][a])
count[i][j][edge] += count[a][j][edge-1];
}
}
}
}
return count[u][v][k];
}
int main() {
int u = 0, v = 3, k = 2;
cout << "There are " << numberOfWalks(u, v, k) << " Possible Walks, from ";
cout << u << " to " << v << " with " << k << " edges.";
}
실행 결과
There are 2 Possible Walks, from 0 to 3 with 2 edges.
예제 그래프에서 정점 0에서 정점 3까지 간선 2개로 도달하는 경로는 0 → 1 → 3과 0 → 2 → 3의 두 가지이므로 결과는 2가 됩니다.
복잡도 분석
간선 수(k+1) × 정점(i) × 정점(j)의 삼중 반복문 안에서 인접 정점(a)을 다시 순회하므로 시간 복잡도는 O(n³ × k)입니다. 공간 복잡도는 3차원 테이블의 크기만큼 O(n² × k)입니다.