[Gold 3] 1520 내리막 길

https://www.acmicpc.net/problem/1520

 

이 문제는 DFS와 DP를 혼합하여 접근해야한다.

DP를 사용해야하는 이유는 단순히 DFS만을 사용해 길을 찾게된다면

(N, M)까지 가는 모든 경로를 탐색해야 하기 때문에 목적지에 갈 수 없는 경우 시간 초과가 발생할 수 있다.

 

따라서 DP를 사용해 목적지에서부터 (0, 0)까지 경로를 저장하면 시간 내에 구할 수 있다.

 

처음 (0, 0)에서 상, 하, 좌, 우로 움직이며

이동할 칸의 값이 작다면 이동 가능한 칸으로 판단한다.

이동이 가능하다면 dp[0][0]에 이동 가능한 칸에 대한 경로를 모두 저장하게 된다.

 

따라서 dp[0][0]이 반환하는 값은 (0, 0)에서 (N, M)까지 갈 수 있는 모든 경로의 수를 저장하게 된다.

 

#include <iostream>
using namespace std;

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

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

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

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

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

    return dp[y][x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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);
}