백준 1520 내리막 길 (C++)

1520번: 내리막 길

dfs와 dp를 응용해서 푸는 문제이다. 단순히 dfs를 사용하여 상하좌우로 모두 탐색을 진행하게되면 시간 초과가 나오게 된다. 즉 dp를 사용해야 한다. 여기서 dp는 현재 위치에서 M-1, N-1까지 도달할 수 있는 경우의 수를 말한다. 탐색을 하는 도중 중복되는 위치를 지나게 되면 더 이상 탐색할 필요 없이 그 위치의 경우의 수를 확인하면 된다. dp를 -1로 초기화하고 방문한 곳은 아직 M-1,N-1에 도달하지 않았기에 0으로 바꿔주었다.
처음 이 문제를 풀 때 단순히 visit를 사용하여 상하좌우로 모두 탐색을 하게 되어 시간 초과가 났었다. dp를 사용해야 한다는 것을 질문 글을 통해 알게되어 많이 아쉬웠다. dfs에서도 dp가 활용될 수 있다는 점을 알아두자.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int M, N;
int A[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int cache[500][500];

int dp(int y,int x) {
    if (y == M - 1 && x == N - 1) return 1;
    if (cache[y][x] != -1) return cache[y][x];

    cache[y][x] = 0;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
        if (A[ny][nx] >= A[y][x]) continue;

        cache[y][x] += dp(ny, nx);
    }

    return cache[y][x];
}

void solution() {
    memset(cache, -1, sizeof(cache));
    
    cout << dp(0, 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> M >> N;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}