[백준] 1520 - 내리막길

dp를 처음 시작하면서 이 문제를 꼭 풀어보면 좋다고 생각하는 문제

dfs로 검사하며 return하는 과정에서 메모이제이션을 해주는 문제로 필수문제라고 생각

1. 맵정보를 입력받으며 dp를 -1로 초기화

2. dfs로 내리막길을 찾으며 탐색

   그 위치에서의 dp는 방문한 것을 체크하기 위해 0으로 만든다.

3. 도착점에 도착하면 1을 반환한다.

4. 만약 방문한 점이고, dp가 -1이 아니라면 그 지점의 값을 반환한다.

#include <iostream>
#define MX 503
using namespace std;
 
int map[MX][MX], dp[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M;
 
int dfs(int x, int y)
{
    if (x == M - 1 && y == N - 1) return 1;
    if (dp[y][x] > -1) return dp[y][x];
    dp[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= M || ny < 0 || ny >= N || map[ny][nx] >= map[y][x]) continue;
        dp[y][x] += dfs(nx, ny);
    }
    return dp[y][x];
}
 
int main(void)
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    cout << dfs(0, 0) << "\n";
    return 0;
}