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

욕심쟁이 판다.

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

<문제>

<코드>

//gcc 4.9.3
 
#include  <stdio.h>
 
int map[501][501];
int visit[501][501];
int N;
 
int max=0;
 
int vectX[4] = {0,1,0,-1};
int vectY[4] = {1,0,-1,0};
 
 
void dfsMap(int y, int x){
    int nextX,nextY;
    int value=0;
    for(int i=0;i<4;i++)
    {
        nextX=x+vectX[i];
        nextY=y+vectY[i];
         
        if(nextX>=N || nextX<0 || nextY>=N || nextY<0)
            continue;
   
        if(map[nextY][nextX] < map[y][x])
        {
            if(visit[nextY][nextX]==0)
                dfsMap(nextY,nextX);
             
             
            if(value<visit[nextY][nextX])
                value=visit[nextY][nextX];
        }
             
    }
     
    visit[y][x] = value+1;
     
    if(max<visit[y][x])
        max=visit[y][x];
}
 
 
 
int main(void)
{
     
    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++)
        {
            if(visit[i][j]==0)
                dfsMap(i,j);
         
        }
    }
       
    printf("%d\n",max);
    return 0;
}

<푸는 요령>

 1. 중요한건 깊이 재귀로 깊이 우선 탐색을 하여서 탐색한 것들을 체크하는 것이다. 

 2. 그렇다면 N * M 맵에서 탐색하는 경우는 N * M 크기 방법밖에 나오지 않기 때문이다. 

 

 3. visit[][] 배열의 초기를 0으로 잡고 1이상의 수는 체크한 것이기 때문에 탐색할 필요가 없는 것이다. 

 4. 즉 이렇게 탐색한것중 가장 큰 숫자가 가장 긴 것이다.