[C++] 백준 1520번 : 내리막 길

[문제]

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

 

 

[접근]

처음에는 dfs로 접근했는데 시간초과가 떴다.

=> 최악의 경우 4^(500 x 500) 만큼의 탐색을 필요로 한다. 

 

그래서 dp로 접근해보았다. 

dp배열의 값들을 -1로 기본설정한다. 방문한적이 없다는 것을 나타낸다. 

방문한적있다면 0 이상의 값이 될것이고 0 이라면 방문은 했지만 길은 없다는 것을 나타낸다. 

 

 

[풀이]

#include <iostream>
using namespace std;

int n,m;
int road[500][500],dp[500][500];
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};

int solve(int x,int y){
    if(x==n-1 && y==m-1) return 1;
    if(dp[x][y]!=-1) return dp[x][y];
    
    dp[x][y]=0;
    
    for(int i=0;i<4;i++){
        int nextx = x+dx[i];
        int nexty = y+dy[i];
        if(nextx>=0 && nexty>=0 && nextx<n && nexty<m && road[nextx][nexty]<road[x][y]){
            dp[x][y] += solve(nextx,nexty);
        }
    }
    return dp[x][y];
}

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

    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>road[i][j];
            dp[i][j]=-1;
        }
    }
    
    cout<<solve(0,0);

    return 0;
}