[백준 c++] 1937 욕심쟁이 판다

문제

https://www.acmicpc.net/problem/1937
n x n 크기의 대나무 숲이 있고 각 지역의 대나무 양이 주어진다.
판다는 상하좌우로 이동할 수 있다.
단, 현재 있는 지역보다 더 많은 대나무가 있는 지역으로만 이동할 수 있을 때,
판다가 어느지역에서 시작해야할 지 구해서
판다가 이동할 수 있는 칸의 수의 최댓값을 출력하는 문제다.

---

풀이

DFS + DP를 이용해서 풀었다.

4방향을 탐색하면서 가장 깊게(멀리) 이동해야한다는 조건은 DFS로 만족시킬 수 있다.

하지만 출발점이 주어지지 않았기 때문에 그냥 DFS로 모든 출발점에 대해서 최대값을 구하면 O(N^4)의 시간복잡도가 나온다. (아마도?)

따라서 DP를 이용해서 시간을 줄여줘야 한다.
dp[y][x] = 이 좌표에서의 최대 이동 칸 수

현재 좌표에서 4방향으로 탐색했을 때, 이동할 수 있는 칸이라면
dp[y][x] = max(dp[y][x], dfs(ny, nx) +1)

---

코드

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

int dfs(int y, int x)
{
    if (dp[y][x])
        return dp[y][x];

    dp[y][x] = 1;

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

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

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

    return dp[y][x];
}

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

    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ret = max(ret, dfs(i, j));

    cout << ret << "\n";
}```