백준 2667- 단지번호붙이기 (https://www.acmicpc.net/problem/2667)
풀이
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int a[30][30];
int group[30][30];
int dx[] = {1, 0, -1, 0}; //동서남북
int dy[] = {0, 1, 0, -1};
int n;
int ans[25*25];
void bfs(int x, int y, int cnt){
queue <pair<int,int>> q;
q.push(make_pair(x,y));
group[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(0<=nx && nx<n && 0<=ny && ny<n){
if(a[nx][ny]==1 && group[nx][ny]==0){
q.push(make_pair(nx,ny));
group[nx][ny]=cnt;
}
}
}
}
}
int main(){
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> a[i][j];
}
}
int cnt=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(a[i][j]==1 && group[i][j]==0){ //새롭게 단지를 돌 준비
bfs(i, j, cnt++);
}
}
}
printf("%d\n",cnt);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
ans[group[i][j]]+=1; //단지별 속하는 집 수 증가
}
}
sort(ans+1, ans+cnt+1);
for (int i=1; i<=cnt; i++) {
printf("%d\n",ans[i]);
}
return 0;
}