1520번 내리막 길

 DP 문제로 분류되어 있지만 DP + DFS 문제이다.

 

 1. cnt 배열을 -1로 초기화하고 DFS를 통해 cnt[M-1][N-1]까지 길을 찾은뒤 돌아오면서 겹치는 다른 길을 찾는다. 찾게 되면 cnt 값을 더해주면서 위치 (0,0)까지 오면 그 값이 정답이 된다.  (cnt 배열을 -1로 초기화하는 이유 : https://www.acmicpc.net/board/view/14670)

 

#include <iostream>
#include <queue>
#define MAX 501
 
using namespace std;
 
int M,N;
int map[MAX][MAX];
int cnt[MAX][MAX];
int ii[4]={1,0,-1,0};
int jj[4]={0,1,0,-1};
 
void solved(int i, int j){
    
    if(cnt[i][j]!=-1){
        return;
    }
    if(i==M-1 && j==N-1){
        cnt[i][j]=1;
        return;
    }
    
    cnt[i][j]=0;
    
    for(int k=0;k<4;k++){
        int ni = i + ii[k];
        int nj = j + jj[k];
        
        if(ni<0 || nj<0 || ni>=M || nj>=N) continue;
        if(map[ni][nj]<map[i][j]){
            solved(ni,nj);
            cnt[i][j]+=cnt[ni][nj];
        }
    }
}
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin >> M >> N;
    
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
            cnt[i][j]=-1;
        }
    }
    
    solved(0,0);
    
    cout << cnt[0][0] << '\n';
}
 

 

 2. 방문처리를 통해 cnt값을 구한다.

 

#include <iostream>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 501
 
using namespace std;
 
int M,N;
bool Check[MAX][MAX];
int map[MAX][MAX];
int cnt[MAX][MAX];
int ii[4]={1,0,-1,0};
int jj[4]={0,1,0,-1};
 
void solved(int i, int j){
    
    if(Check[i][j]==visited){
        return;
    }
    if(i==M-1 && j==N-1){
        cnt[i][j]=1;
        return;
    }
    
    Check[i][j]=visited;
    
    for(int k=0;k<4;k++){
        int ni = i + ii[k];
        int nj = j + jj[k];
        
        if(ni<0 || nj<0 || ni>=M || nj>=N) continue;
        if(map[ni][nj]<map[i][j]){
            solved(ni,nj);
            cnt[i][j]+=cnt[ni][nj];
        }
    }
}
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin >> M >> N;
    
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    
    solved(0,0);
    
    cout << cnt[0][0] << '\n';
}