백준 1520번 - 내리막길

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

오랜만에 문제를 풀다보니 감을 잃어서 헤매다가 겨우 풀었다..

DP에만 집중하다보니 내리막 길을 왼쪽에서 가는 경우와 오른쪽에서 왼쪽으로 가는 경우를

모두 생각해서 (0,0)에서 도착지점까지 가는 방향으로 문제에 접근했다.

당연히 답이 안나와서 한참을 고민하다가 dfs와 dp를 함께 생각해서 문제를 해결했다.

dfs를 통해 좌,우,상,하로 경로를 찾다가 도착지점에 이르면 1을 리턴해준다.

여기서 dp를 함께 사용한다는 것은 이전에 갔던 경로는 해당 위치로 갔을 때 경로의 값을 모두 더해주는 방식이다.

즉, 도착지점에서 시작지점까지 반대로 가는 방식이다.

#include <iostream>
using namespace std;
 
int N,M;
int map[500][500]={0};
int dp[500][500]={0};
int visited[500][500]={0};
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int dfs(int y,int x){
    
    if(y==M-1 && x==N-1)
        return 1;
    
    if(visited[y][x])
        return dp[y][x];
    
    visited[y][x]=1;
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=M || nx<0 || nx>=N)
            continue;
        
        if(map[ny][nx]>=map[y][x])
            continue;
        
        dp[y][x]+=dfs(ny,nx);
    }
    
    return dp[y][x];
}
int main(){
    
    scanf("%d %d",&M,&N);
    
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    
    
    cout<<dfs(0,0)<<endl;
    return 0;
}