이 문제에서는 m×n 크기의 2차원 행렬이 주어지며, 행렬의 왼쪽 위(좌상단)에서 오른쪽 아래(우하단)까지 이동할 수 있는 모든 경로를 출력해야 합니다.
단, 탐색 시에는 행렬 안에서 오른쪽 또는 아래 방향으로만 이동할 수 있다는 제약 조건이 있습니다.
예제를 통해 문제를 더 쉽게 이해해 보겠습니다.
입력:
1 3 5
2 8 9
출력:
1 -> 3 -> 5 -> 9
1 -> 3 -> 8 -> 9
1 -> 2 -> 8 -> 9
접근 방법
이 문제는 재귀(Recursion)를 활용하여 해결할 수 있습니다. 현재 위치한 칸(cell)에서 아래 또는 오른쪽으로 한 칸씩 이동하면서 지나온 경로를 기록하고, 각 단계마다 재귀 호출을 반복하는 방식입니다.
탐색 과정은 다음과 같이 진행됩니다.
- 현재 칸의 값을 경로 배열(path)에 저장합니다.
- 아래쪽 칸으로 이동하는 경우와 오른쪽 칸으로 이동하는 경우, 두 가지에 대해 각각 재귀 호출을 수행합니다.
- 현재 위치가 마지막 행(i == m-1)에 도달하면 남은 열들을 모두 경로에 추가한 뒤 경로를 출력합니다.
- 현재 위치가 마지막 열(j == n-1)에 도달하면 남은 행들을 모두 경로에 추가한 뒤 경로를 출력합니다.
구현 예제
위의 재귀 알고리즘을 구현한 C++ 프로그램은 다음과 같습니다.
#include<iostream>
using namespace std;
void printPathTPtoBR(int *mat, int i, int j, int m, int n, int *path, int pi) {
// 마지막 행에 도달한 경우, 남은 열의 값들을 경로에 추가 후 출력
if (i == m - 1) {
for (int k = j; k < n; k++)
path[pi + k - j] = *((mat + i*n) + k);
for (int l = 0; l < pi + n - j; l++)
cout << path[l] << " ";
cout << endl;
return;
}
// 마지막 열에 도달한 경우, 남은 행의 값들을 경로에 추가 후 출력
if (j == n - 1) {
for (int k = i; k < m; k++)
path[pi + k - i] = *((mat + k*n) + j);
for (int l = 0; l < pi + m - i; l++)
cout << path[l] << " ";
cout << endl;
return;
}
// 현재 칸의 값을 경로에 저장한 뒤, 아래와 오른쪽 방향으로 재귀 탐색
path[pi] = *((mat + i*n) + j);
printPathTPtoBR(mat, i+1, j, m, n, path, pi + 1); // 아래로 이동
printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1); // 오른쪽으로 이동
}
void findPath(int *mat, int m, int n) {
int *path = new int[m+n];
printPathTPtoBR(mat, 0, 0, m, n, path, 0);
}
int main() {
int mat[2][3] = { {1, 2, 3}, {4, 5, 6} };
cout << "행렬의 왼쪽 위에서 오른쪽 아래까지의 경로 :\n";
findPath(*mat, 2, 3);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같이 행렬의 좌상단에서 우하단까지의 모든 경로가 출력됩니다.
1 4 5 6
1 2 5 6
1 2 3 6
출력 결과를 보면 2×3 행렬에서 오른쪽과 아래 방향으로만 이동할 때 만들 수 있는 총 3가지 경로가 모두 표시된 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 가능한 경로의 수에 비례하며, m×n 행렬에서 가능한 경로의 개수는 조합 공식으로 계산하면 C(m+n-2, m-1)개입니다.