[백준 c++] 1520 내리막 길

문제

https://www.acmicpc.net/problem/1520
N x M 크기의 격자판으로 각 높이가 쓰여있는 지도가 있다.
상하좌우로 이동할 수 있는데 현재 칸보다 높이가 더 낮은 칸으로만 이동할 수 있다.
맨 왼쪽 위에서 시작해서 제일 오른쪽 아래까지 가는 경우의 수를 구하는 문제다.

---

풀이

✅ DFS + DP

dfs + dp를 이용해서 풀는 문제는 2가지로 나뉘는 것 같다.

① 최대값 구해라
dp값을 비교해가면서 최대값을 dfs돌린 것과 dp값 중 최대값을 구한다.
dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1)

② 모든 경우의 수 구해라
dfs값을 더하기
dp[y][x] += dfs(ny, nx)

✅ dp를 -1로 초기화

이 문제에서 또 하나 중요한 포인트는 dp를 -1로 초기화 해야 한다는 것이다.

왜냐하면 각 dp에는 (n,m)까지 갈 수 있는 경우의 수를 저장하는데
이 값이 0일 수 있기 때문이다.

그래서 -1로 초기화하지 않으면 이미 방문해서 최대값이 0으로 정해졌지만
탐색을 안했다고 여기고 다시 탐색을 해서 시간초과가 일어날 수 있다.

memset(dp, -1, sizeof(dp))

---

코드

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m, a[501][501], dp[501][501];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};

int dfs(int y, int x)
{
    if (y == n - 1 && x == m - 1)
        return 1;

    if (dp[y][x] != -1)
        return dp[y][x];

    dp[y][x] = 0;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny >= n || nx >= m || ny < 0 || nx < 0)
            continue;

        if (a[y][x] > a[ny][nx])
            dp[y][x] += dfs(ny, nx);
    }

    return dp[y][x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    memset(dp, -1, sizeof(dp));

    int ret = dfs(0, 0);
    
    if (ret == -1)
        cout << 0 << "\n";
    else
        cout << ret << "\n";
}