백준 2583번 영역 구하기 C++

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

 

bfs로 해결할 수 있는 문제이다. 처음에 좌표의 시작점이 왼쪽 아래 (0, 0) 이라 조금 헷갈렸지만 그냥 배열처럼

왼쪽 위 (0, 0)에서 시작해도 결과는 같다. 모양은 위아래로 뒤집어진 모양이 나오지만 영역의 개수와 넓이에는 변화가 없을 것이니 그렇게 해결하기로 했다.

두 번째 줄부터 x1, y1, x2, y2의 좌표가 주어지는데, x는 열, y는 행의 좌표이기 때문에 

row1 = y1

col1 = x1

row2 = y2

col2 = x2 라고 저장한 뒤 이 좌표로 둘러싸인 직사각형의 공간을 채워졌다고 표시하고, bfs방식으로 해결하였다. visited 배열을 만들기 귀찮아서 방문한 좌표는 채워졌다고 변경하면서 탐색하였다. 직사각형을 돌면서 채워지지 않은 곳을 발견하면 cnt를 올리고 size를 1로 초기화 한 뒤 bfs로 탐색하면서 주변에 채워지지 않은 곳이 있을 때마다 size를 늘렸다. 그리고 탐색이 끝나면 정답을 저장하는 벡터에 size를 추가했다. 모든 좌표의 탐색이 끝나면 cnt를 출력하고 ans벡터를 오름차순 정렬한 뒤 출력하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int m, n, k, x1, y1, x2, y2;
	cin >> m >> n >> k;
	vector<vector<int>> v(m, vector<int>(n, 0));
	for (int i = 0; i < k; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		int row1 = y1;
		int col1 = x1;
		int row2 = y2;
		int col2 = x2;
		for (int j = row1; j < row2; j++) {
			for (int k = col1; k < col2; k++) {
				v[j][k] = 1;
			}
		}
	}
	int cnt = 0;
	vector<int> ans;
	queue<pair<int, int>> q;
	//bfs
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] == 0) {
				cnt++;
				int size = 1;
				q.push({ i,j });
				v[i][j] = 1;
				while (!q.empty()) {
					auto a = q.front();
					q.pop();
					if (a.first - 1 >= 0 && v[a.first - 1][a.second] == 0) {
						v[a.first - 1][a.second] = 1;
						size++;
						q.push({ a.first - 1,a.second });
					}
					if (a.first + 1 < m && v[a.first + 1][a.second] == 0) {
						v[a.first + 1][a.second] = 1;
						size++;
						q.push({ a.first + 1,a.second });
					}
					if (a.second - 1 >= 0 && v[a.first][a.second - 1] == 0) {
						v[a.first][a.second - 1] = 1;
						size++;
						q.push({ a.first,a.second - 1 });
					}
					if (a.second + 1 < n && v[a.first][a.second + 1] == 0) {
						v[a.first][a.second + 1] = 1;
						size++;
						q.push({ a.first,a.second + 1 });
					}
				}
				ans.push_back(size);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << cnt << "\n";
	for (auto a : ans) {
		cout << a << " ";
	}
};