[C++]BOJ 2667 - 단지번호붙이기

지도를 배열에 저장하고 칸별로 분기를 돌며 집이 있는 칸을 만나면 인접한 집들을 탐색한다.
위 과정을 반복해 단지를 나누고 집의 수를 벡터에 저장한 후 정렬해 출력한다.
bfs dfs 두 방법 모두 다뤄보겠다.

두 방법 모두 한번 탐색한 집은 배열에서 삭제하므로 다음 분기에서 중복탐색하지 않는다.
덕분에 bfs에서 삭제 횟수가 해당 단지의 집 수가 된다.

bfs는 처음으로 집을 발견한 위치를 기준으로 상하좌우를 탐색하며 큐에 넣는다.
탐색하며 삭제한 집의 갯수가 곧 단지내의 집 수이기 때문에 그 값을 리턴한다.
리턴된 값을 벡터에 넣고 정렬 후 출력한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, v[27][27], sx, sy, sc, cnt;
queue<int> qx, qy;
vector<int> ans;
int bfs(int x, int y) {
	cnt = 0;
	qx.push(x), qy.push(y);
	while(!(qx.empty() && qy.empty())) {
		sx = qx.front(); qx.pop();
		sy = qy.front(); qy.pop();
		if(!v[sy][sx]) continue;
		v[sy][sx] = 0; cnt++;
		if(v[sy - 1][sx]) qx.push(sx), qy.push(sy - 1);
		if(v[sy + 1][sx]) qx.push(sx), qy.push(sy + 1);
		if(v[sy][sx - 1]) qx.push(sx - 1), qy.push(sy);
		if(v[sy][sx + 1]) qx.push(sx + 1), qy.push(sy);
	}
	return cnt;
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			scanf("%1d", &v[i][j]);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(v[i][j]) ans.push_back(bfs(j, i));
	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++)
		cout << ans[i] << endl;
}

dfs를 사용한 방법도 마찬가지로 지도 전체를 돌며 집을 발견한 위치를 시작점으로 탐색을 수행한다.
상하좌우 더 이상 이동할 공간이 없을때까지 재귀적으로 탐색하고 1씩 더해나간다.
최종적으로 dfs 탐색과정을 트리를 그리면 최하단 노드에는 1이 담기고 각 부모노드에는 자식노드 들의 합이 담겨있는 형태가 될 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, arr[27][27];
vector<int> ans;
int dfs(int x, int y) {
	if(!arr[y][x]) return 0;
	arr[y][x] = 0;
	return dfs(x - 1, y) + dfs(x + 1, y) + dfs(x, y - 1) + dfs(x, y + 1) + 1;
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			scanf("%1d", &arr[i][j]);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(arr[i][j]) ans.push_back(dfs(j, i));
	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++)
		cout << ans[i] << endl;
}