BOJ 2667 : 단지번호붙이기

BOJ 2667

[BOJ 2667(S1) 리뷰]

 

전에 풀었던 영역구하기 문제와 아주 유사하다. (아니 오히려 쉽다)

영역구하기 문제는 입력값에 대해 집적 칠해야하는 번거로움이 있었지만

이 문제는 배열을 통째로 줘서 아주 편하다.

 

영역구하기 코드에서 보드판을 string으로 바꾼거 빼면 코드가 거의 흡사하다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

string board[26];
bool check[26][26];
priority_queue <int, vector<int>, greater<int>> result;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

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

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

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[i][j] != 0 || board[i][j] != '1') continue;
			int area = 0;
			queue <pair<int, int>> Q;
			check[i][j] = 1;
			Q.push({ i,j });
			cnt++;
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				area++;
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if (board[nx][ny] != '1' || check[nx][ny] != 0) continue;
					check[nx][ny] = 1;
					Q.push({ nx,ny });
				}
			}
			result.push(area);
		}
	}

		cout << cnt << '\n';
		int size = result.size();
		while (!result.empty())
		{
			cout << result.top() << ' ';
			result.pop();
		}

}