2583_영역 구하기

▶실버1

풀이

2차원 bfs문제. 점을 기준으로 탐색하는게 아니라 영역기준이므로 다음과 같은 형태로 정사각형 네 꼭짓점 중 왼쪽 아래를 기준으로 잡는다.

x, y 값이 주어지면 for문으로 해당 범위 내의 arr[x][y]의 값을 true로 바꿔준다. 모든 범위가 주어지고 나면 (0, 0)부터 (n - 1, m - 1)까지 돌며 bfs 실행.

 

코드

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;

queue <pair<int, int>> q;
int r[4] = { 1, -1, 0, 0 };
int c[4] = { 0, 0, 1, -1 };
bool arr[251][251];
int land;
vector <int> ans;

int bfs(int n, int m) {
	int cnt = 1;
	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 + r[i];
			int ny = y + c[i];
			if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
				if (arr[nx][ny] == false) {
					arr[nx][ny] = true;
					cnt++;
					q.push({ nx, ny });
				}
			}
		}
	}
	return cnt;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int m, n, k;
	cin >> m >> n >> k;
	while(k--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = y1; i < y2; i++) {
			for (int j = x1; j < x2; j++) {
				arr[i][j] = true;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == false) {
				arr[i][j] = true;
				q.push({ i, j });
				land++;
				int tmp = bfs(n, m);
				ans.push_back(tmp);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << land << "\n";
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
}