[백준] 1937번. 욕심쟁이 판다

[문제]

 

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

[풀이]

 

판다는 대나무를 다 먹어 치우면 상,하,좌,우 중 하나로 이동할 수 있다.

단, 이전에 먹었던 대나무보다 많은 대나무가 존재하는 곳으로만 이동할 수 있다.

판다가 최대한 살 수 있는 일수를 구하면 된다.

 

DP 배열에 해당 위치에서 이동할 수 있는 최대 거리를 저장했다.

따라서 DFS 함수를 통해 미리 DP 배열의 값을 구해놨다면 DP 배열에 저장된 값을 return  하면 된다.

아직 DP 배열에 0이 저장되어 있다면 다시 DFS 함수를 호출하여 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하면 된다.

 

아래 코드와 같이 DFS 함수를 통해 (1,1) ~ (N,N)까지 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하여 최댓값을 구하면 된다. 

 

 

[코드]

 

시간 : 128ms

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int DP[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int dx[4] ={-1,1,0,0};
int dy[4] ={0,0,-1,1};
int res=0;
int N;


int DFS(int x, int y)
{
    if(DP[x][y])   return DP[x][y];
    DP[x][y] =1;
    
    for(int i=0;i<4;i++){
        
        int nx= x+dx[i];
        int ny= y+dy[i];
        
        if(nx < 0 || ny <0 || nx >= N || ny >= N)   continue;
        if(map[nx][ny] <= map[x][y])    continue;
        
        DP[x][y] = max(DP[x][y] , DFS(nx,ny)+1);
        

    }
    return DP[x][y];
}


int main(void)
{
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            res = max(res , DFS(i,j));
        }
    }
    cout << res;
    
    return 0;
    
}