[BFS, 난이도 중하] 백준 2667번 단지번호붙이기

이 문제 같은 경우에는 1의 그룹이 몇개인가를 찾으면 된다.

이중 for문으로 방문되지 않은 '1' 요소를 찾아 그 좌표를 큐에 넣고 BFS를 수행해주면 된다.

맨 먼저 (0,1) 좌표를 중심으로 bfs가 수행되며 7개의 '1'이 첫 그룹으로 묶일 것이다.

bfs과정중 (0,2) 좌표도 방문처리가 되었으므로 이중 for문에서 (0,2)는 넘어가게 될 것이고 (0,4)좌표를 중심으로

두번 째 그룹핑을 수행할 것이다.

그룹핑이 끝날 때마다 즉, while문을 탈출할 때마다 단지번호를 1씩 늘려가며 마지막에 최종 단지번호를 출력하면 문제가 해결된다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int map[26][26];
bool visited[26][26];
vector<int> house;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	int group = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				int housecount = 1;
				visited[i][j] = true;
				q.push(make_pair(i, j));
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++) {
						if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
						if (map[x + dx[k]][y + dy[k]] == 1 && !visited[x + dx[k]][y + dy[k]]) {
							q.push(make_pair(x + dx[k], y + dy[k]));
							visited[x + dx[k]][y + dy[k]] = true;
							housecount++;
						}
					}
				}
				house.push_back(housecount);
				group++;
			}
		}
	}
	cout << group << "\n";
	sort(house.begin(), house.end());
	for (int i = 0; i < house.size(); i++) cout << house[i] << "\n";
}