발상
이전 단계의 정수 삼각형 문제와 유사하지만 이번 문제는 상하좌우 모두 이동이 가능하다는 차이점이 있다.
단순하게 순차적으로 방문하며 이전 경로에 저장된 최적값을 이용해 계산하는 방법은 사용할 수 없다. 어떤 순서로 방문해도 상하좌우가 모두 연산되어 있을 수는 없기 때문이다.
문제를 봤을 때 가장 중요한 점은 모든 경로가 반드시 일방통행이라는 점이다.
즉, 이전 지점을 검사할 때 이전 지점에서 다시 현재 지점이 경로로 검색되는 순환이 발생하지 않는다.
따라서 높이 조건만 검사해도 재귀 호출 시 별도의 방문 여부 확인 없이 경로를 확인하는 것이 가능하다. 만약 양방향 통행이 가능하다면 무한 재귀를 방지하기 위해 특정 경로를 이미 방문했는지 여부를 검사해야 한다.
풀이 개념 자체는 정수 삼각형 문제와 똑같지만 4방향을 모두 검사해야하기 때문에 Bottom-Up이보단 Top-Down 풀이가 훨씬 용이하단 차이가 있다.
점화식
점화식이 복잡해보이지만 4방향 중 현재 위치로 올 수 있는 위치의 경우의 수를 다 더하는 것 뿐이다.
코드
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> arr, dp;
int mvr[4] = { 0, 1, 0, -1 };
int mvc[4] = { 1, 0, -1, 0 };
int f(int r, int c) {
if (dp[r][c] != -1) return dp[r][c];
int s = 0;
for (int i = 0; i < 4; i++) {
int mr = r + mvr[i];
int mc = c + mvc[i];
if (mr < 1 || mc < 1 || mr > n || mc > m || arr[r][c] >= arr[mr][mc]) continue;
s += f(mr, mc);
}
return dp[r][c] = s;
}
int main() {
cin >> n >> m; arr = dp = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
dp[1][1] = 1; // 시작점 -> 시작점 경우 수 1가지 ( 기저 사례 )
cout << f(n, m);
return 0;
}