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

 

1) 문제설명

백준 Online Judge 2583번 영역 구하기

 

2) 아이디어

처음 M,N 행렬을 0으로 초기화 한 뒤 입력받은 위치(X1 X2 ~ Y1 Y2)는 1로 변경해 주었다.

이후 BFS를 실행하여 영역크기는 각각 vector에 저장하여 오름차순으로 출력하였고 영역의 개수는 따로 카운트 하였다.

 

3) 코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;
queue<pair<int, int>> q;
int arr[101][101];
int range[101][101];
int result = 0;
int cnt = 0;
int n, m, k;
int x1, y11, x2, y2;
void bfs(int y, int x) {
	result = 1;
	range[y][x] = 1;
	int dx[4] = { -1,1,0,0 };
	int dy[4] = { 0,0,-1,1 };
	while (q.size()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx <0 || ny <0 || nx >= m || ny >= n || arr[ny][nx] == 1) {
				continue;
			}
			if (range[ny][nx]) {
				continue;
			}
			range[ny][nx] = 1;
			result += 1;
			q.push({ ny,nx });
		}

	}
}
int main() {
	vector<int> v;
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			arr[i][j] = 0;
		}
	}
	for (int i = 0; i < k; i++) {
		cin >> x1 >> y11 >> x2 >> y2;
		for (int x = x1; x < x2; x++) { // 
			for (int y = y11; y < y2; y++) {
				arr[y][x] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			result = 0;
			if (range[i][j] == 0 && arr[i][j] == 0) {
				cnt++;
				q.push({ i,j });
				bfs(i, j);
			}
			if (result != 0) {
				v.push_back(result);
			}
		}
	}
	sort(v.begin(), v.end());
	cout << cnt << '\n';
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}

}