1937 욕심쟁이 판다

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

판다가 대나무를 먹으면서 이동한다. 단, 현재 위치의 대나무보다 더 많은 대나무가 있는 쪽으로만 이동한다. 이 때 판다가 이동할 수 있는 최대 길이를 찾는 문제이다. 먼저 DFS를 이용한 완전 탐색을 생각해 볼 수 있다. 그러나 N이 최대일 때, 500*500의 map에서 모든 경로를 다 탐색하면 시간 초과가 나게 된다. 이 때 다이나믹을 이용해서 가지치기를 한다. d[x][y] = 판다가 (x,y)까지 올 수 있는 최대 길이라고 정의하자. 경로를 탐색하다가 d[x][y]가 지금까지 온 경로의 길이 k보다 크다면 이미 다른 경로로 왔을 때의 최대 길이가 존재한다는 뜻이다. 이 경우 더 이상 탐색하는 것이 의미가 없으므로 탐색을 종료한다. 즉, DFS+DP로 문제를 해결할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,map[500][500],d[500][500],ans;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
void dfs(int x,int y,int k)
{
    if(d[x][y]>k) return;
    ans=max(ans,d[x][y]=k);
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || map[x][y]>=map[nx][ny])
            continue;
        dfs(nx,ny,k+1);
    }
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        dfs(i,j,1);
    printf("%d",ans);
    return 0;
}