[BOJ] 2667번 : 단지번호붙이기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 
int board[28][28]; 
bool isvis[28][28];
int dx[4] = { 0,1,0,-1 }; 
int dy[4] = { 1,0,-1,0 };
queue<pair<int, int>> Q; 
vector<int> v;
int n; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 0; i < n; i++) {
		string x; 
		cin >> x; 
		for (int j = 0; j < n; j++) {
			board[i][j] = x[j] - '0';
		}
	}
	int aparts = 0; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!board[i][j]) continue; 
			if (isvis[i][j]) continue;
			aparts++; 
			int cnt = 1; 
			Q.push({ i,j }); 
			isvis[i][j] = true; 
			while (!Q.empty()) {
				auto cur = Q.front(); Q.pop(); 
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.X + dx[dir]; 
					int ny = cur.Y + dy[dir]; 
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
					if (board[nx][ny] <= 0) continue;
					if (isvis[nx][ny]) continue; 
					isvis[nx][ny] = true; 
					cnt++;
					Q.push({ nx,ny });
				}
			}
			v.push_back(cnt);
		}
	}
	cout << aparts << '\n'; 
	sort(v.begin(), v.end()); 
	for (int i = 0; i < v.size(); i++) cout << v[i] << '\n';
}

bfs를 이용해서 풀었다. 여기서는 기존의 bfs문제인 0을 찾는 게 아니라, 1을 찾아야 한다. isvis 배열을 두어, 이미 방문한 곳은 방문하지 않았다. 또한, apart와 cnt라는 변수를 두어서, 각각 몇 호인지, 각호에 몇 개의 동이 있는지를 기록하였다. 

이후 vector에 추가했다.