[어려워요알고리즘] BOJ 1520 : 내리막길

Info

• 백준 1520번 내리막길
• Gold 4 solved.ac
• 다이나믹 프로그래밍

Write UP

다이나믹 프로그래밍 문제입니다.
상하좌우 이동이 가능하고, 현재 값보다 크기가 작은 곳으로만 갈 수 있어요.

일반적으로 생각하면 dfs를 돌려서 모든 경로를 찾아내면 되겠지만, 배열의 크기가 너무 커서 시간초과가 발생할 것 같네요.

따라서 dp로 접근해야 합니다!!

사실 dfs인데 그냥 값을 저장하기 때문에 탐색이 줄어든다는 것이 전부에요.

탐색하면서 밟은 곳을 전부 1씩 더해주는 원리이기 때문에 마지막 발판에서 모든 경우가 더해져요.

go(1, 1) 부터 시작합니다.
상하좌우 갈 수 있는 곳을 찾고, 그 곳이 자신보다 작으면 재귀로 계속 호출해요.

결론적으로 재귀함수가 오른쪽으로 쭉 펼져질 것이고, 리턴이 되면서 왼쪽으로 한 칸씩 오는 거죠.

#include <iostream>
using namespace std;

int N, M;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int map[504][504];
int dp[504][504];
int cnt;

int go(int cy, int cx) {
    if (cy == N && cx == M) {
        return 1;
    }
    int &ret = dp[cy][cx];
    if (ret != -1) {
        return ret;
    }
    ret = 0;
    for (int i = 0; i < 4; i++) {
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        if (ny >= 1 && ny <= N && nx >= 1 && nx <= M) {
            if (map[ny][nx] < map[cy][cx]) {
                ret += go(ny, nx);
            }
        }
    }
    return ret;
}

int main() {
    for (int i = 0; i < 504; i++) {
        for (int j = 0; j < 504; j++) {
            dp[i][j] = -1;
        }
    }
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    printf("%d\n", go(1, 1));
    return 0;
}