문제 개요
양의 정수로 이루어진 2차원 행렬이 주어졌을 때, 왼쪽 위 시작 칸 (0, 0)에서 오른쪽 아래 마지막 칸 (n-1, n-1)까지 이동하는 데 필요한 최소 단계 수를 구하는 문제입니다.
현재 위치가 (i, j)인 경우, 다음 두 가지 방식으로만 이동할 수 있습니다.
- (i, j + mat[i][j]) : 현재 칸에 적힌 값만큼 오른쪽으로 이동
- (i + mat[i][j], j) : 현재 칸에 적힌 값만큼 아래쪽으로 이동
단, 행렬의 경계를 벗어나는 이동은 허용되지 않습니다.
예시 행렬
| 2 | 1 | 2 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
위 행렬의 경우 정답은 2입니다. 실제 이동 경로는 다음과 같습니다.
(0, 0) → (0, 2) → (2, 2)
시작 칸의 값이 2이므로 오른쪽으로 두 칸 이동해 (0, 2)에 도착하고, 다시 그 칸의 값 2만큼 아래로 이동하여 목적지 (2, 2)에 도달합니다.
동적 계획법(Dynamic Programming) 접근
이 문제는 동적 계획법과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 각 칸 (i, j)에서 목적지 (n-1, n-1)까지 도달하는 데 필요한 최소 단계 수를 저장하는 테이블을 만들고, 다음 점화식을 사용합니다.
DP[i, j] = 1 + min(DP[i + arr[i][j], j], DP[i, j + arr[i][j]])
즉, 현재 칸에서 이동 가능한 두 방향(오른쪽, 아래쪽) 중 더 적은 단계가 필요한 쪽을 선택하고, 이동 자체에 1단계를 더해주는 방식입니다. 이미 계산된 칸은 다시 계산하지 않도록 하여 중복 연산을 제거합니다.
C++ 구현 예제
#include<iostream>
#define N 3
using namespace std;
int table[N][N];
bool temp_val[N][N];
int countSteps(int i, int j, int arr[][N]) {
if (i == N - 1 and j == N - 1)
return 0;
if (i > N - 1 || j > N - 1)
return INT_MAX;
if (temp_val[i][j])
return table[i][j];
temp_val[i][j] = true;
table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr));
return table[i][j];
}
int main() {
int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } };
int ans = countSteps(0, 0, arr);
if (ans >= INT_MAX)
cout << -1;
else
cout <<"Number of steps: "<< ans;
}코드 설명
- table 배열 : 각 칸에서 목적지까지의 최소 단계 수를 저장하는 메모이제이션 테이블입니다.
- temp_val 배열 : 해당 칸의 값이 이미 계산되었는지 여부를 표시합니다.
- 목적지에 도달하면 0을 반환하고, 행렬 범위를 벗어나면 INT_MAX를 반환하여 도달 불가능함을 나타냅니다.
- 결과가 INT_MAX보다 크거나 같으면 경로가 존재하지 않으므로 -1을 출력합니다.
실행 결과
Number of steps: 2
이 알고리즘은 각 칸을 최대 한 번씩만 계산하므로 시간 복잡도는 O(n²), 공간 복잡도 역시 메모이제이션 테이블 때문에 O(n²)입니다. 완전 탐색으로 모든 경로를 확인하는 것보다 훨씬 효율적으로 최소 단계 수를 구할 수 있습니다.