C++로 행렬을 순회하는 방법의 수 구하기

row × col 크기의 2차원 행렬이 주어졌을 때, 셀 (0,0)에서 출발하여 셀 (row, col)까지 도달하는 경로의 가짓수를 구하는 것이 목표입니다. 단, 이동은 오른쪽 또는 아래쪽 방향만 허용됩니다. 즉, 첫 번째 이동은 (0,0)에서 (0,1)(아래) 또는 (1,0)(오른쪽)으로 갈 수 있으며, 대각선 이동(1,1)은 불가능합니다.

예시

입력

col = 2; row = 4

출력

행렬을 순회하는 방법의 수: 4

설명

(0,0)에서 (2,4)까지 도달할 수 있는 경로는 다음 그림과 같습니다.

입력

col = 4; row = 3

출력

행렬을 순회하는 방법의 수: 10

설명

문제를 더 작은 재귀 호출로 나누어 해결합니다.
먼저 col=3, row=2인 경우의 방법 수를 구하고, 다음으로 col=2, row=1인 경우를 구하는 식으로 진행합니다.
col=1 또는 row=1일 때의 답은 항상 1입니다. (오른쪽 또는 아래쪽으로만 직진하는 경우)

프로그램에서 사용된 접근 방식

이 접근 방식에서는 재귀(Recursion)를 활용합니다. 행(row) 또는 열(col)이 1이 되면 오직 한 가지 방법, 즉 오른쪽으로만 쭉 이동하거나 아래쪽으로만 쭉 이동하는 경우뿐입니다. 이 조건이 재귀 호출의 종료 조건(base case)이 됩니다.

• 행렬의 차원을 나타내는 정수 row와 col을 입력받습니다.

• 함수 ways_traverse_matrix(int row, int col)는 차원 값을 받아 행렬을 순회할 수 있는 방법의 수를 반환합니다.

• row == 1인 경우 1을 반환합니다.

• col == 1인 경우 1을 반환합니다.

• 그 외의 경우에는 재귀 호출을 통해 ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2)를 계산합니다.

• 여기서 temp_1은 이전 행 번호, temp_2는 이전 열 번호를 의미합니다.

• 최종적으로 전체 경로의 가짓수를 얻게 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int ways_traverse_matrix(int row, int col){
   if (row == 1){
      return 1;
   }
   else if(col == 1){
      return 1;
   } else {
      int temp_1 = row − 1;
      int temp_2 = col − 1;
      return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
   }
}
int main(){
   int col = 2;
   int row = 2;
   cout<<"행렬을 순회하는 방법의 수: "<<ways_traverse_matrix(row, col);
   return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

행렬을 순회하는 방법의 수: 2