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

문제

입출력

풀이

BOJ 1926번 그림이랑 비슷한 문제이다.
단지의 개수와 각 단지내의 집의 수를 오름차순으로 구하는 문제이다.
BFS를 이용해서 풀 수 있으며 시작점이 여러개인것을 인지하고 입력을 문자열 형식으로 받는것만 주의하면 쉽게 해결할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 27

char board[SIZE][SIZE];
bool vis[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;

	vector<int> V;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> board[i][j];

	int num = 0; // 배추흰지렁이의 수
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (vis[i][j] || board[i][j] == '0') continue;
			num++;
			queue<pair<int, int>> Q;
			vis[i][j] = 1;
			Q.push({ i,j });

			int area = 0;
			while (!Q.empty())
			{
				area++;
				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 (vis[nx][ny] || board[nx][ny] == '0') continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
				}
			}
			V.push_back(area);
		}
	}
	cout << num << '\n';
	sort(V.begin(), V.end());
	for (auto e : V)
		cout << e << '\n';
}