[BaekJoon/백준] 1520번 내리막 길

 

오늘 컨디션이 너무 안좋다.

 

세종병원에 심장진료를 받으려 예약하려 했는데, 아침부터 전화해서 연결해달라고 했는데

저녁될때까지 전화 남겨준다고만 하고 전화를 안줬다. 게다가 저녁이 다 되어서야 내일 전화준다고 한다 ㅎ..

 

 

---

각설하고,,

 

이번 문제는 DP 문제이다.

1890번 점프 문제와 아주 유사한 문제이다.

 

위 링크에 나와있는 메모이제이션, 타뷸레이션 두 방법 중 메모이제이션 방법을 사용했다.

 

그리고 DP 정의는 아래와 같다.

DP[x][y] = x,y 에서 목적지까지 가는 경로 수

 

---

 

 내리막길이기 때문에, 역 경로는 존재하지 않으니 왔던길은 다시 돌아가지 않기에 우선 무한루프를 돌 가능성이 없다.

 => 1890번 유형과 결국 비슷하다.

 

상하좌우를 통해 모든 경우의 수를 구하되, 무한루프를 주의해야하는데, 기본적으로 무한루프를 돌지 않으니 신경 써 줄 필요 없다.

 

 

 

 모든 노드를 한번씩 방문 시도하면서,

1. 방문(DFS) 안했으면 DFS 하거나

2. 이미 DFS 했는데 방문하려하면 DP값을 이용한다.

 

 

 DFS를 아직 안했다(방문 안했다) => DP 값은 -1

 DFS를 처리했다 => DP 값은 0 이상

#include <iostream>

using namespace std;

int N, M;

int MAP[500][500];
int DP[500][500];

int mx[4] = {1, 0, -1, 0};
int my[4] = {0, 1, 0, -1};


int dfs(int x, int y) {
    
    if(x == N - 1 && y == M - 1)
        return 1;
    
    
    if(DP[x][y] == -1) { // x,y에서 DFS를 계산한 적이 없다면
        
        DP[x][y] = 0;
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            
            if(MAP[tx][ty] < MAP[x][y]) {
                
                DP[x][y] += dfs(tx, ty); // x,y에서 상하좌우 끝에 목적지에 도달할 수 있는 수 총합 구하는 과정임.
                
            }
        }
        return DP[x][y];

        
    } else
        return DP[x][y];
        
    
}

int main() {
    
    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) << "\n";
    
    
}

 

시간복잡도는, 결국 모든노드 방문처리 + 상하좌우를 통해 DP값 획득을 생각하여 일반적인 상하좌우 VISIT 처리 문제와 동일한 시간복잡도를 갖게 될 것이다. ( = VISIT 처리가 DP값 유무 처리와 같은 것)

 

 

 

소요 시간 : 1시간 20분