[백준][1520번][DP] 내리막길

내리막길

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

<코드>

#include <stdio.h>
 
 
int map[510][510] = {};
int visit[510][510] = {};
int M, N;
 
struct saveMap{
    int x;
    int y;
};
 
saveMap make_saveMap(int x, int y){
    saveMap temp;
    temp.x = x; temp.y = y;
    return temp;
}
 
int serch(int x, int y){
 
    int vect_x[5] = { 0, 1, 0, -1, 0 };
    int vect_y[5] = { 0, 0, 1, 0, -1 };
 
    if (x == N && y == M)
        return 1;
    if (visit[y][x]) return visit[y][x];
    for (int i = 1; i <= 4; i++){
        int nextX = x + vect_x[i];
        int nextY = y + vect_y[i];
        if (map[nextY][nextX] < map[y][x] && nextX>0 && nextX <= N && nextY>0 && nextY <= M){
 
            visit[y][x] += serch(nextX,nextY);
 
        }
    }
 
    return visit[y][x];
}
int main(void){
 
 
 
    scanf("%d %d", &M, &N);
 
    for (int i = 1; i <= M; i++)
        for (int j = 1; j <= N; j++)
            scanf("%d", &map[i][j]);
 
    
    printf("%d\n", serch(1,1));
    return 0;
}

<문제 푼 요령>

1. 이 문제는 내리막 길만 찾기 때문에 경로가 한쪽 경로이다. 즉 싸이클이 이루어 질 수 없다.

2. 완전 탐색이나 BFS를 이용해서 풀어볼려고 했으나 메모리 제한이나, 시간 제한이 걸려서 풀 수 없었다.

3. 즉 DFS를 이용한 DP로 문제를 풀어야 한다.

4. 각 현재의 값에 대해서 4방향을 검색해서 얻게 되는 경우수를 더하면서 진행한다.  즉 끊임 없이 파고 들지만 이미 파고들어서 나온 결과값을 그대로 사용하는 것이다. 

5. return에 대한 값은 우리가 마지막 위치에 도달할때 1을 리턴해줘서 어떻게 보면 파고드는건 위에서 부터인데 채워지는것은 아래서부터라고 보면 맞다.

6. 그리고 한번 갔던 곳에 대해서는 또다시 갈 필요없기 때문에 여기서 또 가지치기를 해준다. 

7. 어떻게 동작하는지는 아래 그림으로 표현했다.