[BOJ] 2583 : 영역구하기 - travelbeeee

문제 : https://www.acmicpc.net/problem/2583

---

[알고리즘풀이]

bool map[i][j] : ( i, j ), ( i + 1, j ), ( i, j + 1 ), ( i + 1, j + 1) 4개의 점으로 이루어진 영역이 채워져 있는지 아닌지.

먼저, 직사각형 입력을 받아 map[i][j] 를 채워준다.

그 후, map[i][j] 중 빈 공간에 대해서 BFS 탐색을 진행하며 영역의 크기와, 영역의 개수를 세준다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int m, n, k, a1,a2,a3,a4;
bool map[100][100]; // map[i][j] : (i, j) (i + 1, j + 1)까지 크기 1인 정사각형
bool cmap[100][100];

int dir_x[4] = { -1, 0, 1, 0 };
int dir_y[4] = { 0, -1, 0, 1 };

bool check(int a, int b) {
	if (0 <= a && a < m && 0 <= b && b < n)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		cin >> a1 >> a2 >> a3 >> a4;
		for (int j = a1; j < a3; j++)
			for (int l = a2; l < a4; l++)
				map[j][l] = 1;
	}
	vector<int> s;
	int c = 0;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == false && cmap[i][j] == false) {
				c++;
				int count = 0;
				queue<pair<int, int>> q;
				q.push(make_pair(i, j));
				cmap[i][j] = true;
				while (!q.empty()) {
					pair<int, int> x = q.front();
					q.pop();
					int s_x, s_y;
					for (int i = 0; i < 4; i++) {
						s_x = x.first + dir_x[i];
						s_y = x.second + dir_y[i];
						if (check(s_x, s_y)) {
							if (cmap[s_x][s_y] == false && map[s_x][s_y] == false) {
								q.push(make_pair(s_x, s_y));
								cmap[s_x][s_y] = true;
							}
						}
					}
					count++;
				}
				s.push_back(count);
			}
		}
	}
	sort(s.begin(), s.end());
	cout << c << '\n';
	for (int i = 0; i < s.size(); i++)
		cout << s[i] << ' ';
}

---