이 튜토리얼에서는 m×n 크기의 행렬에서 왼쪽 상단 칸부터 오른쪽 하단 칸까지 이동할 수 있는 경로의 총 개수를 구하는 프로그램을 살펴봅니다.
여기서는 각 단계마다 오른쪽 또는 아래쪽으로 한 칸씩만 이동할 수 있다고 가정합니다. 이 조건에서 시작점에서 끝점까지 도달할 수 있는 모든 가능한 경로의 수를 계산하는 것이 우리의 과제입니다.
접근 방식
가장 직관적인 방법은 재귀를 활용하는 것입니다. 현재 위치에서 끝점까지 도달할 수 있는 경로의 수는 다음 두 경우의 합과 같습니다.
- 아래쪽 칸에서 출발하여 끝점에 도달하는 경로의 수
- 오른쪽 칸에서 출발하여 끝점에 도달하는 경로의 수
행이나 열이 1개뿐인 경우에는 이동할 선택지가 없으므로 경로는 항상 1개입니다.
예제 코드
#include <iostream>
using namespace std;
// 가능한 경로의 개수를 반환하는 함수
int count_paths(int m, int n) {
if (m == 1 || n == 1)
return 1;
return count_paths(m - 1, n) + count_paths(m, n - 1);
}
int main() {
cout << count_paths(3, 3);
return 0;
}
실행 결과
6
위 코드는 3×3 행렬을 대상으로 실행되었으며, 그 결과 총 6개의 경로가 존재함을 확인할 수 있습니다.
동작 원리
count_paths(m, n) 함수는 다음과 같이 재귀적으로 동작합니다.
m == 1 || n == 1: 행 또는 열이 하나뿐이면 더 이상 방향을 선택할 수 없으므로 1을 반환합니다.- 그 외의 경우에는 아래쪽으로 이동한 경우
count_paths(m - 1, n)와 오른쪽으로 이동한 경우count_paths(m, n - 1)의 값을 더해 반환합니다.
성능 개선 팁
순수 재귀 방식은 같은 하위 문제를 반복해서 계산하므로 시간 복잡도가 지수적으로 증가합니다(O(2^(m+n))). 따라서 행렬의 크기가 커질수록 실행 시간이 급격히 늘어납니다. 실무에서는 메모이제이션(Memoization)이나 동적 계획법(DP)을 적용해 시간 복잡도를 O(m×n)까지 최적화하는 것이 좋습니다.