[알고리즘 문제] 백준1937 - 욕심쟁이 판다

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

조건을 만족하면서 판다가 가장 멀리 움직일 수 있는 경로를 구하는 문제 입니다. 그냥 일반적인 dfs방식으로 풀면 4^500의 시간복잡도를 가지므로 dfs + dp로 문제를 해결해야 합니다.

 

먼저 dp[][]를 모두 -1로 초기화 해주어야 하는데 이는 아직 해당 좌표를 한번도 방문한 적이 없다는 것을 의미합니다. 만약 dp[][]값이 -1이면 검사를 해주어야 하고 dp[][]값이 -1이 아닌 경우는 해당 위치의 값을 바로 return 해줍니다.

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int arr[501][501];
int dp[501][501];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int N;

int dfs(int y, int x)
{
    if (dp[y][x] == -1)
    {
        dp[y][x] = 1;
        int tmp = 0;
        for (int i = 0; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];

            if (newY >= 0 && newX >= 0 && newY < N && newX < N && arr[newY][newX] > arr[y][x])
            {
                tmp = max(tmp, dfs(newY, newX));
            }
        }
        dp[y][x] += tmp;
    }
    return dp[y][x];
}

int main()
{

    cin >> N;

    queue<pair<int, int>> que;

    for (int y = 0; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            cin >> arr[y][x];
            dp[y][x] = -1;
            que.push({y, x});
        }
    }
    int ans = -1;
    while (!que.empty())
    {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();

        dp[y][x] = dfs(y, x);
        ans = max(dp[y][x], ans);
    }

    cout << ans << endl;
    return 0;
}