백준[1520] - 내리막 길

문제

백준 1520 문제 보기

접근 방법

아직은 bottom-up 방식이 익숙치가 않아 거의 모든 다이나믹 문제를 top-down으로 접근하고 있다. 이번 문제도 마찬가지로 top-down 방식으로 접근했다.

동서남북으로 검사하되 범위 안에 있고 내리막일 경우 계속 진행하는 식으로 문제를 풀었다. 제대로 푼것 같았지만 제출했을때 시간초과가 났다. 이유는 길이 없는 경우를 따로 dp에 저장하지 않아 이전에 이미 검사했음에도 불구하고 계속 계산을 진행해 시간 초과가 났다.

이를 해결하기위해 dp[r][c] = 0으로 초기화를 했다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int M, N;
int map[505][505];
int chk[505][505];
int dp[505][505];

int rr[4] = {-1, 0, 1, 0};
int cc[4] = {0, 1, 0, -1};

int dfs(int r, int c) {
    // 접근했던 곳인지 체크
    if(dp[r][c] != -1) {
        return dp[r][c] ;
    }
    // 도착지점 확인
    if(r == M && N == c) {
        return 1;
    }

    // dp에 갈수 없는 경우를 미리 저장
    dp[r][c] = 0;
    // 동서남북
    for(int i = 0; i < 4; i ++) {
        int nextR = r + rr[i];
        int nextC = c + cc[i];
        // 범위체크
        if(nextR >= 1 && nextC >= 1 && nextR <= M && nextC <= N) {
            // 방문하지 않았고 내리막 길 일 경우
            if(!chk[nextR][nextC] && map[nextR][nextC] < map[r][c]) {
                // 방문 체크
                chk[nextR][nextC] = 1;
                // dp에 새로운 값 저장
                dp[r][c] += dfs(nextR, nextC);
                chk[nextR][nextC] = 0;
            }
        }
    }
    return dp[r][c];
}

int main() {
    cin >> M >> N;
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= M; i ++) {
        for(int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    chk[1][1] = 1;
    dfs(1, 1);
    cout << dp[1][1];
    return 0;
}