[백준/2667] 단지번호붙이기

bfs로 풀었습니다

 

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

2667번: 단지번호붙이기

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[30][30];
bool check[30][30];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 }; //위 아래 오른쪽 왼쪽
queue<pair<int, int>> q;

int n;
int cnt = 0;
vector<int> ans;

void bfs(int x, int y) {
	pair<int, int> p;
	p = make_pair(x, y);
	q.push(p);
	cnt++;
	check[x][y] = true;
	while (!q.empty()) {
		int sx = q.front().first;
		int sy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = sx + dx[i];
			int ny = sy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
				continue;
			}
			else {
				if (map[nx][ny] == 1 && check[nx][ny] != true) {
					p = make_pair(nx, ny);
					q.push(p);
					check[nx][ny] = true;
					cnt++;
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && check[i][j] != true) {
				cnt = 0;
				bfs(i, j);
				ans.push_back(cnt);
			}
		}
	}

	cout << ans.size() << '\n';
	sort(ans.begin(), ans.end());

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << '\n';
	}

	return 0;
}