문제 개요
m×n 크기의 2차원 행렬이 주어졌을 때, 행렬의 왼쪽 위(첫 번째 셀)에서 오른쪽 아래(마지막 셀)까지 이동할 수 있는 모든 경로를 출력하는 것이 이 문제의 목표입니다. 탐색 시에는 상하좌우 네 방향, 즉 왼쪽·오른쪽·위·아래 어느 방향으로든 이동할 수 있습니다.
네 방향 중 오른쪽과 위쪽 이동은 실제로 사용 빈도가 낮지만, 특정 조건에서는 유용하게 활용될 수 있습니다.
예제
입력:
1 3 5 2 8 9
출력:
1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9
접근 방법
이 문제는 재귀(백트래킹) 방식으로 해결할 수 있습니다. 한 셀에서 다음 셀로 이동할 때마다 지나온 값을 경로 배열에 저장하고, 경로가 끝점에 도달할 때마다 지금까지 쌓인 경로를 출력하는 구조입니다.
알고리즘의 동작 순서는 다음과 같습니다.
- 현재 셀 (i, j)의 값을 경로 배열에 저장합니다.
- 현재 위치가 마지막 행이라면, 남은 오른쪽 셀들을 경로에 덧붙인 뒤 전체 경로를 출력하고 종료합니다.
- 현재 위치가 마지막 열이라면, 남은 아래쪽 셀들을 경로에 덧붙인 뒤 전체 경로를 출력하고 종료합니다.
- 그렇지 않다면 아래쪽 (i+1, j)과 오른쪽 (i, j+1) 두 방향에 대해 각각 재귀 호출을 수행합니다.
아래는 이 재귀 알고리즘을 구현한 프로그램입니다.
구현 예제
#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<<"Path from top-left to bottom-right of matrix are :\n";
findPath(*mat, 2, 3);
return 0;
}
실행 결과
Path from top-left to bottom-right of matrix are : 1 4 5 6 1 2 5 6 1 2 3 6
네 방향 이동으로 확장하기
위 코드는 설명의 단순화를 위해 아래쪽과 오른쪽 두 방향만 사용했습니다. 왼쪽·위쪽 이동까지 포함하는 진정한 4방향 탐색으로 확장하려면 방문 여부를 기록하는 2차원 bool 배열(visited)이 반드시 필요합니다. 4방향 이동을 허용하면 같은 셀을 다시 지나는 순환(cycle)이 발생할 수 있으므로, 셀에 들어갈 때 방문 표시를 하고 재귀 호출이 끝난 뒤 방문 표시를 해제하는 백트래킹 처리를 함께 해주어야 무한 재귀를 피할 수 있습니다.
참고로, 아래·오른쪽 이동만 허용할 경우 m×n 행렬의 총 경로 수는 조합 공식 C(m+n−2, m−1)로 계산할 수 있습니다. 예를 들어 2×3 행렬이라면 C(3, 1) = 3개의 경로가 존재하며, 위 실행 결과와 정확히 일치합니다.