문제 푼 날짜 : 2021-10-01

문제

문제 링크 : https://www.acmicpc.net/problem/1520

접근 및 풀이

DP와 DFS를 이용한 그래프 탐색문제이다.
문제에 입력으로 주어진 지도의 (0, 0)부터 시작하여 (M-1, N-1)까지 도달할 때까지 DFS로 탐색한다.
탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에서 (M-1, N-1)까지가는 경로가 몇 개가 존재하는지이다.
이를 이용하여 탐색하면서 dp 배열을 업데이트시켜주었다.

코드

// 백준 1520번 : 내리막 길
#include <iostream>
#include <cstring>

using namespace std;

int M, N;
int arr[501][501];
int dp[501][501];

int D[4][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};

int dfs(int y, int x) {
    if (y == M - 1 && x == N - 1) {
        return 1;
    }
    int &ret = dp[y][x];
    if (ret != -1) {
        return ret;
    }
    
    ret = 0;
    for (int i = 0; i < 4; i++) {
        int nextY = y + D[i][0];
        int nextX = x + D[i][1];
        
        if (nextY < 0 || nextY >= M || nextX < 0 || nextX >= N) {
            continue;
        }
        if (arr[nextY][nextX] < arr[y][x]) {
            ret += dfs(nextY, nextX);
        }
    }
    return ret;
}

int main() {
    cin >> M >> N;

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

결과

피드백

DP가 들어가면 항상 어려운 것 같다...