[C] 2667: 단지번호붙이기

이 문제는 앞서 풀었던 미로 탐색 문제와 매우매우매우 흡사하다

공통점으로는 일단 그래프 끝까지 모두 탐색을 해야하고 이걸 저정해야하며

BFS 알고리즘을 사용해서 풀어야했던 것인데 사실 DFS 알고리즘을 써도 풀렸을 것이다.

그래도 미로탐색 문제가 생각이 나서 BFS로 풀게 돠었다

 

BFS 알고리즘을 사용할 떄 전역 변수를 잘 사용해야하고 nx,ny를 잘 사용하여 범위를 정해

최대한 간결하면서도 이해하기 쉽게 코드를 정리하는게 중요한 것 같다.

또한 queue 배열을 사용해야하는데 아직 이에 익숙치 않아 더 공부해야겠다.

 

차이점으로 미로탐색 문제는 맨 마지막 좌표까지 도달하는 최단 경로를 찾는 문제였고

이번 문제는 단지를 찾아서 단지 안에 있는 아파트를 찾는 것이다.

또 다른 차이점은 여러가지 그래프가 생성된다는 것이었고 각 그래프가 몇개인지 확인해야 했던 것이다.

 

그리고 어이없게도 정렬때문에 시간을 오래써먹었는데

쉽지만 그래도 정확하게 문제를 푸는 연습을 해야겠다.

 

#include <stdio.h>

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

int bfs(int n,int y,int x)
{
  int cnt=1;
  int front=1;
  int rear=1;
  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>n || ny>n|| nx<1 || ny<1) //그래프를 벗어남
            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;
            cnt++;
          }
               
        }
      
      front++; //하나가 끝남 ->지워줘야함
      
    }
  return cnt;
  
}

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

    printf("%d\n",cnt);
    if(cnt==1)
    {
       printf("%d",count_house[1]);
      return 0;
    }
     
    for(int i=1;i<=cnt;i++)
      {
        
        for(int j=i+1;j<=cnt;j++)
          {
            if(count_house[j]<count_house[i])
            {
              int tmp=count_house[j];
              count_house[j]=count_house[i];
              count_house[i]=tmp;
              
            }
          }
        printf("%d\n",count_house[i]);
      } 
       
      
  }