이 문제에서 mXn 2D 행렬이 주어지고 행렬의 왼쪽 상단에서 오른쪽 하단까지 가능한 모든 경로를 인쇄해야 합니다. 탐색의 경우 행렬에서 오른쪽과 아래쪽으로만 이동할 수 있습니다.
주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -
Input: 1 3 5 2 8 9 Output: 1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9
이 문제를 해결하기 위해 우리는 한 셀에서 다른 셀로 이동하고 아래로 내려가는 경로를 인쇄합니다. 행렬의 각 셀에 대해 이를 재귀적으로 수행합니다.
예시
재귀 알고리즘을 구현하는 프로그램을 보자 :
#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-rigth of matrix are :\n"; findPath(*mat, 2, 3); return 0; }
출력
행렬의 왼쪽 상단에서 오른쪽 하단까지의 경로는 -
1 4 5 6 1 2 5 6 1 2 3 6