[C/C++ 백준 2667번] 단지번호붙이기 (Silver 1)

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

DFS이든 BFS이든 방법은 상관없이, 모든 그래프를 탐색하면서 모든 집을 세어주면 된다. 각 단지의 수도 세어주어야하므로 dfs밖의 변수를 만들어 새로운 집을 세줄때마다(dfs를 진행할 때마다) 저장해주자.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int array[27][27], ans=0, cnt=0, housen = 1;
int house[500];
bool visit[27][27];
int xmove[4] = {-1, 1, 0 ,0};
int ymove[4] = {0, 0, 1, -1};
void dfs(int x, int y){
	visit[x][y] = true;
	for(int i=0; i<4; i++){
		if(visit[x+xmove[i]][y+ymove[i]]==false
		&& array[x+xmove[i]][y+ymove[i]]==1){
			dfs(x+xmove[i], y+ymove[i]);
			housen++;
		}
	}
}
int main(void){
	int N;
	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			visit[i][j] = false;
		}
	}
	memset(array, 0, 27*27*sizeof(int));
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf("%1d", &array[i][j]);
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			if(visit[i][j]==false && array[i][j]==1){
				ans++;
				dfs(i, j);
				house[cnt]=housen;
				housen = 1;
				cnt++;
			}
				
		}
	}
	sort(house, house+cnt);
	printf("%d\n", ans);
	for(int i=0; i<cnt; i++)
		printf("%d\n", house[i]);
}