백준 1937번 - 욕심쟁이 판다

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

예전에 if문으로 간신히 시간초과를 해결했던 문제를 다시 풀어보았다.

핵심은 dp와 메모이제이션이다.

dp[y][x]를 (y,x)좌표에서 가장 멀리 갈 수 있는 길이라고 할 때

dfs를 통해서 dp[y][x]가 값이 있다면 이미 예전에 (y,x)좌표에서 가장 멀리 갈 수 있는 길이를 구했다고 생각하고

다시 구할 필요없이 dp[y][x]를 리턴해준다.

만약에 이전에 가지 않았다면 dp[y][x]를 1로 설정한 뒤에

상하좌우 4방향으로 dfs탐색을 통해 갈 수 있다면 1씩 값을 더 해주는 방식으로 탐색하면 된다.

#include <iostream>
using namespace std;
 
int dp[500][500]={0};
int map[500][500]={0};
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int n;
 
int len=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<0 ||ny>=n || nx<0 || nx>=n)
            continue;
        
        if(map[y][x]>=map[ny][nx])
            continue;
        
        dp[y][x]=max(dp[y][x],dfs(ny,nx)+1);
        
    }
    
    return dp[y][x];
}
int main(){
    
    cin>>n;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&map[i][j]);
        }
    }
    
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ans=max(ans,dfs(i,j));
        }
    }
    cout<<ans<<endl;
    return 0;
}