[C] 1012: 유기농 배추

이 문제도 결국 앞서 풀었던 2667 단지번호붙이기 문제와 매우 유사하다.

단지의  수를 구한 것과 마찬가지로 이 문제도 배추의 집단의 수를 구하면 됐던 것이고 

이를 위해서 BFS 알고리즘을 활용하여 풀었다.

 

다만 여기서 주의해야 했던 점은 배추의 배치가 고정되어 있지 않고 테스트케이스마다 달라지기 때문에

그때마다 다시 arr과 visit 배열을 초기화 해줘야 했던 것이다.

 

#include <stdio.h>

int visit[51][51]; // 지나갔는지 확인
int arr[51][51]; //그래프를 저장
int queue[2800][2];
int x_jump[4]={1,0,-1,0}; //오른쪽, 아래로, 왼쪽, 위로
int y_jump[4]={0,1,0,-1};

int bfs(int max_y,int max_x,int y,int x)
{
 
  int front=0;
  int rear=0;
  queue[front][0]=x;
  queue[front][1]=y;
  rear++;
  
  while(front<rear)
    {
      x=queue[front][0];
      y=queue[front][1];
      for(int i=0;i<4;i++)
        {
          int nx=x+x_jump[i];
          int ny=y+y_jump[i];
          if(nx>=max_x || ny>=max_y|| nx<0 || ny<0) //그래프를 벗어남
            continue;
          if(arr[ny][nx]==0) //집이 없음
            continue;
          
          if(visit[ny][nx]==0) //아직 지나가지 않음
          {
            queue[rear][0]=nx;
            queue[rear][1]=ny;
            rear++;
            visit[ny][nx]=1;
          
          }
               
        }
      
      front++; //하나가 끝남 ->지워줘야함
      
    }

  
}

  int main(void)
  {
   int t,x,y,k;
    scanf("%d",&t);
    for(int p=1;p<=t;p++)
    {
        scanf("%d %d %d",&x,&y,&k);
        for(int j=0;j<k;j++)
       {
         int a,b;
         scanf("%d %d",&a,&b);
         arr[b][a]=1;
        }
      int cnt=0;  
      
      for(int j=0;j<y;j++)
        {
          for(int i=0;i<x;i++)
            {
              if(arr[j][i]==1&&visit[j][i]==0) //집 있는데 아직 안지나감
              {  
                visit[j][i]=1;
                bfs(y,x,j,i);
                ++cnt;
              }
           }
       }

      /*for(int j=0;j<y;j++)
        {
          for(int i=0;i<x;i++)
            {
              printf("%d ",visit[j][i]);
            }
          printf("\n");
        }*/
      printf("%d\n",cnt);

      for(int j=0;j<51;j++) //배열 초기화해줌
        {
          for(int i=0;i<51;i++)
            {
              arr[i][j]=0;
              visit[i][j]=0;
            }         
        }      
    }    
      
  }