백준 2583번 영역 구하기

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

 

아이디어:

1. 직사각형 k에 대해 board[i][j] = 1 로 하고 2중 for문으로 board[i][j] == 0 && vis[i][j] == 0 을 찾아 큐에 넣으면서 BFS

2. 큐에 넣으면서 num++; 넓이로 저장할 area는 큐에서 빼면서 ++한 뒤, area가 0이 아닐 때 벡터 areas에 삽입

3. 벡터 areas를 sort()로 정렬해서 num 뒤에 출력

 

n과 m이 각각 y축, x축을 가리 키는 것에 주의

y축에서, 그림을 상하 반전 시켜도 넓이는 그대로이므로

문제 그림에 충실해서 for문을 반대로 돌리는 등 별도 처리하지 않아도 된다.

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

char board[1001][1001];
int vis[1001][1001];
int m, n;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int k, x1, x2, y1, y2;
	int num = 0, area = 0;
	cin >> m >> n >> k;
	queue<pair<int, int>> Q;
	vector<int> areas;

	while (k--) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = y1; i < y2; i++) {
			for (int j = x1; j < x2; j++) {
				board[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {

			area = 0;

			if (board[i][j] == 0 && vis[i][j] == 0) {
				vis[i][j] = 1;
				Q.push({ i, j });
				num++;
			}

			while (!Q.empty()) {
				pair<int, int> 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 >= m || ny < 0 || ny >= n) continue;
					if (board[nx][ny] != 0 || vis[nx][ny] != 0) continue;
					vis[nx][ny] = 1;
					Q.push({ nx, ny });
				}
			}

			if (area) areas.push_back(area);
		}
	}

	cout << num << "\n";
	sort(areas.begin(), areas.end());
	for (auto x : areas) cout << x << " ";

	return 0;
}