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

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

전형적인 BFS 유형의 문제입니다.

2583번과 거의 동일한 문제였습니다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int map[26][26];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int BFS(int sx, int sy) {
	int cnt = 1;
	queue<pair<int, int > > q;
	q.push({ sx, sy });
	map[sx][sy] = 0;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 0) continue;
			q.push({ nx, ny }); 
			map[nx][ny] = 0;
			cnt++;
		}
	}
	
	return cnt;
}


int main(void) {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
	int answer = 0;
	vector<int> v;
    
    scanf("%d", &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) {
    			answer++;
    			v.push_back(BFS(i, j));
			}
		}
	}
	
	sort(v.begin(), v.end());
	cout << answer << "\n";
	for(int i = 0; i < v.size(); i++) {
		cout << v[i] << "\n";
	}
}