Baekjoon 1520 (내리막 길)

Baekjoon 1520, 백준 1520 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>

using namespace std;

int M, N;
int map[502][502] = {0,};
int dp[502][502] = {0,};    // number of cases from map[i][j] to end

int func(int i, int j){
    // starts from map[i][j]
    // Dynamic Programming: if already value exists, use it

    if(dp[i][j] != -1){  // dp[i][j] = -1 : not visited
        return dp[i][j];
    }

    else {
        dp[i][j] = 0;

        if(map[i+1][j] < map[i][j] && i+1 <= M) {
            // move to map[i+1][j]
            dp[i][j] += func(i+1, j);
        }

        if(map[i-1][j] < map[i][j] && i-1 >= 1){
            // move to map[i-1][j]
            dp[i][j] += func(i-1, j);
        }

        if(map[i][j+1] < map[i][j] && j+1 <= N){
            // move to map[i][j+1]
            dp[i][j] += func(i, j+1);
        }

        if(map[i][j-1] < map[i][j] && j-1 >= 0){
            // move to map[i][j-1]
            dp[i][j] += func(i, j-1);
        }
    }

   return dp[i][j];
}

int main() {
    scanf("%d %d", &M, &N);

    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            scanf("%d", &map[i][j]);
            dp[i][j] = -1;
        }
    }

    // start from map[1][1]
    // find every cases
    dp[M][N] = 1;
    int answer = func(1,1);
    printf("%d\n", answer);
}

동적계획법 문제로, 새로운 아이디어가 접목되었다.
dp 배열의 값 설정을 통해 “방문 여부”를 따지는 아이디어이다.
실제로 방문 여부를 따지지 않고 코드를 짜면, 시간 초과가 발생하였다.

본 코드에서는 처음 dp 배열을 -1 로 초기화하였고, 이를 “방문하지 않았다”는 것의 여부로 사용하였다.
즉 dp != -1 이라면 이미 한 번 방문한 적이 있는 칸이라는 것이다.

특별한 조치를 하지 않는다면 전역 변수로 선언한 dp 배열은 0으로 초기화가 될 것이며,
이는 “아직 값을 계산하지 않아서 0” 인 것과, “계산을 해 보았는데 방법의 수가 0”인 것을 구별할 수 없다.

따라서 -1 을 사용하여 이를 구별하고, 시간을 줄여 준다.