백준 2583 영역 구하기 (C++)

2583번: 영역 구하기

bfs를 이용한 문제이다. 먼저 주어지는 직사각형의 위치에 해당하는 곳을 true로 바꿔주었다. 그 후 반복문을 돌며 false인 위치를 찾아 이를 카운트한 후 bfs를 해주었다. bfs를 하면서 사이즈를 카운트해 벡터에 저장해주었다. 영역의 개수와 오름차순으로 정렬된 카운트한 사이즈들을 출력해주었다.
간단한 bfs 문제여서 금방 풀 수 있었다.

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

using namespace std;

int M, N, K, res = 0;
bool A[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<int> area;

void bfs(int a, int b) {
	queue<pair<int, int>> q;
	int count = 0;

	q.push({ a,b });
	A[a][b] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		count++;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
			if (A[ny][nx]) continue;

			q.push({ ny,nx });
			A[ny][nx] = true;
		}
	}

	area.push_back(count);
}

void solution() {
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (!A[i][j]) {
				bfs(i, j);
				res++;
			}
		}
	}

	sort(area.begin(), area.end());

	cout << res << endl;
	for (auto elem : area) {
		cout << elem << " ";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> M >> N >> K;

	for (int i = 0; i < K; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		for (int m = b; m < d; m++) {
			for (int n = a; n < c; n++) {
				A[m][n] = true;
			}
		}
	}

	solution();
	
	return 0;
}