[1937] 욕심쟁이 판다

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

<문제>

bfs를 사용하면 큐가 터진다.

dp를 사용한 dfs를 구현해야 500*500의 맵에서도 2초안에 답을 구할 수 있다.

dp[i][j] = (i, j)에서 시작했을때의 최적해로 구성해준다. 

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, a[501][501];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int dp[501][501];
int f(int cy, int cx) {
    int y, x, i;
    if (dp[cy][cx])return dp[cy][cx];
    dp[cy][cx] = max(dp[cy][cx],1);
    for (i = 0; i < 4; i++) {
        y = cy + dy[i];
        x = cx + dx[i];
        if (y < 0 || x < 0 || y >= n || x >= n)continue;
 
        if (a[cy][cx] < a[y][x]) {
            dp[cy][cx]=max(dp[cy][cx],f(y, x)+1);
        }
    }
    return dp[cy][cx];
}
int main(void) {
    int i, j,ans=0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
 
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            ans = max(ans, f(i, j));
    printf("%d", ans);
    return 0;
}