BOJ 2667 단지번호붙이기

- 큐를 이용하여  BFS 탐색하는 기본 문제

- 두번째 풀 때는 단지 내부에 있는 집의 개수를 세기 위해 vector를 이용하려고 했는데 잘 안됐다.

다음 번에는 벡터로 풀어봐야겠다.

- DFS 로도 풀어봐야겠다!

 

 

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

 

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int n, cnt;
int map[26][26];
int visited[26][26];
int ans[26*26];

int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};

void bfs(int x, int y, int cnt){
  queue<pair<int, int> > q;
  q.push(make_pair(x,y));
  visited[x][y]=cnt;

  while(!q.empty()){
    x = q.front().first;
    y = q.front().second;
    q.pop();

    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){
        if(visited[nx][ny]==0 && map[nx][ny]==1){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=cnt;
        }
      }
    }
  } //while end
}

int main(){
  scanf("%d", &n);

  for(int i=0; i<n; i++){
    ans[i]=0;
    for(int j=0; j<n; j++){
      scanf("%1d", &map[i][j]);
      visited[i][j]=0;
    }
  } // input end

  cnt=0;
  for(int i=0; i<n; i++){ // 전체 지도 탐색하기
    for(int j=0; j<n; j++){
      if(visited[i][j]==0 && map[i][j]==1){
        bfs(i,j,++cnt);
      }
    }
  }

 for(int i=0; i<n; i++){
   for(int j=0; j<n; j++){
     ans[visited[i][j]] += 1;
     // visited 원소 (1,2,3)의 갯수 세기.
   }
 }

 //output field
 printf("%d\n", cnt);
 sort(ans+1, ans+cnt+1);

 for(int i=1; i<=cnt; i++){
   printf("%d\n", ans[i]);
 }
}