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

2667번: 단지번호붙이기

 

 

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#define MAX 26
using namespace std;

int n, home;
int map[MAX][MAX];
int v[MAX][MAX];
vector<int>town;

bool go (int a, int b) {
	if (v[a][b] == true)return false;
	if (map[a][b] == 0) return false;
	if (a<1 || b<1 || a>n || b>n) return false;
	v[a][b] = true; home++;
	return true;
}


void bfs(int a, int b) {
	
	home = 1;
	queue < int>y, x;
	y.push(a), x.push(b);

	while (!x.empty()) {
		int cy = y.front();y.pop();
		int cx = x.front();x.pop();
		
	    v[cy][cx] = true;

		if (go(cy+1, cx)) y.push(cy+1), x.push(cx);
		if (go(cy-1, cx)) y.push(cy-1), x.push(cx);
		if (go(cy, cx+1)) y.push(cy), x.push(cx+1);
		if (go(cy, cx-1)) y.push(cy), x. push(cx-1);

	}
	town.push_back(home);
}


int main() {

	cin >> n;

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			char h;
			cin >> h;
			map[i][j] = h-'0';
		}
	}

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			if (map[i][j] == 1 && v[i][j] == false) {
				bfs(i, j);
			}
		}
	}

	sort(town.begin(), town.end());

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

	return 0;
}