[BOJ 2583 // C++] 영역 구하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2583번 문제인 영역 구하기이다.
문제는 아래 링크를 확인하자.

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

2583번: 영역 구하기

주어지는 영역의 크기가 크지 않으므로, 직접 직사각형에 포함되는 칸을 반복문으로 칠한 뒤 connected component의 개수를 세어주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int R, C;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
bool board[100][100];

int bfs(int r, int c) {
	int ret = 0;
	queue<pair<int, int>> que;
	que.push({ r,c });
	while (!que.empty()) {
		ret++;
		r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc]) continue;
			board[rr][cc] = 1;
			que.push({ rr,cc });
		}
	}

	return ret;
}

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

	int K; cin >> R >> C >> K;
	while (K--) {
		int r1, c1, r2, c2; cin >> c1 >> r1 >> c2 >> r2;
		for (int r = r1; r < r2; r++) {
			for (int c = c1; c < c2; c++) {
				board[r][c] = 1;
			}
		}
	}

	vector<int> ans;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c]) continue;
			board[r][c] = 1;
			ans.emplace_back(bfs(r, c));
		}
	}

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

	cout << ans.size() << '\n';
	for (auto a : ans) cout << a << ' ';
}