[bfs] 삼성이의 재난 예측

삼성재난센터에서는 장마철 재난에 대처하고자 어떤 지역의 높이 정보를 파악하여 그 지역에 많은 비가 내렸을 경우 물에 잠기지 않는 안전한 영역의 개수를 조사하려고 한다. 

이 때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 

예) 5*5행렬인 지역의 높이 정보가 아래와 같을 때 결과 예시이다.

물에 잠긴영역을 표시하면 아래와 다음과 같이 변하게 된다.

 

위의 그림에서 안전한 영역은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 or 왼쪽으로 인접해 있으며 그 크기가 최대인 영역으로, 위의 높이 4이하가 잠기는 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭지점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급!) 

 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 안전한 영역의 최대 개수를 찾는 프로그램을 작성하라.

 

입력 형식

가장 먼저 전체 테스트 케이스 개수를 입력받는다.

이후 아래와 같이 입력을 차례대로 받는다.

첫째 줄에는 지역을 나타내는 행과 열의 개수 N이 입력( N = 2 <= 100 )

둘째 줄부터 지역의 높이 정보를 행렬에 맞게 입력 된다. (높이 = 1 <= 100)

 

출력 형식

물에 잠기지 않는 안전한 영역의 최대 개수 출력

(반드시 각 입력에 대한 출력 전에 #testcase숫자 출력 후 결과를 출력한다. 개행 필수)

 

입/출력의 예

입력 출력

1

5

6 8 2 6 2

3 2 3 4 6

6 7 3 3 2

7 2 5 3 6

8 9 5 2 7

#testcase1

5

 
#include <stdio.h>
 
#define MAX 105
 
int N;
int Map[MAX][MAX];
int Map2[MAX][MAX];
 
int Que[MAX*MAX][2];
int Front, Rear;
int hMax=0;
 
void enQue(int x, int y)
{
    Que[Rear][0] = x;
    Que[Rear][1] = y;
    Rear++;
}
 
void deQue(int* x, int* y)
{
    *x = Que[Front][0];
    *y = Que[Front][1];
    Front++;
}
 
void resetQue()
{
    Front = 0;
    Rear = 0;
}
 
void input()
{
    int i, j;
    scanf("%d", &N);
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=N; j++)
        {
            scanf("%d", &Map[j][i]);
            if(hMax < Map[j][i])
                hMax = Map[j][i];
        }
    }    
}
 
void bfs(int x, int y, int h)
{
    int i;
    int qx, qy;
    int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
 
    resetQue();
    Map2[x][y] = h;
    enQue(x, y);
 
    while(Front < Rear)
    {
        deQue(&qx, &qy);
        for(i=0; i<4; i++)
        {
            if(Map[qx+dir[i][0]][qy+dir[i][1]] > h 
                &&  Map2[qx+dir[i][0]][qy+dir[i][1]] != h)
            {
                Map2[qx+dir[i][0]][qy+dir[i][1]] = h;
                enQue(qx+dir[i][0], qy+dir[i][1]);
            }
        }
    }
}
 
void process()
{
    int i, j, h;
    int count=0;
    int max=0;
 
    for(h=1; h<=hMax; h++)
    {
 
        count=0;
        for(i=1; i<=N; i++)
        {
            for(j=1; j<=N; j++)
            {
                if(Map[i][j] > h && Map2[i][j] != h)
                {
                    count++;
                    bfs(i, j, h);
                }
            }
        }
        if(max < count)
            max = count;
    }
    printf("%d\n", max);
}
 
 
int main()
{
 
    int itr;
    int i,j;
    int nCount;        /* 문제의 테스트 케이스 */
 
    scanf("%d", &nCount);    /* 테스트 케이스 입력 */
 
    for(itr=0; itr<nCount; itr++)
    {
 
        printf("#testcase%d\n",itr+1);
        input();
        process();
        for(i=1; i<=N; i++)
        {
            for(j=1; j<=N; j++)
            {
                Map[j][i]=0;
                Map2[j][i]=0;
            }
        }    
    }
 
    return 0; 
 
}