[BOJ] 2583. 영역 구하기

문제

www.acmicpc.net/problem/2583

2583번: 영역 구하기

---

해설

 

(x1, y1) ~ (x2, y2) 까지 배열의 값을 1로 변경 후 (0, 0)부터 dfs탐색을 통해 나온 결과 값을 벡터에 값을 넣어준다.

---

코드

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

using namespace std;

int map[101][101];
int cnt;
int m, n, k;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

void dfs(int x, int y) {

	if (map[x][y] == 0) {
		map[x][y] = 1;
		cnt++;
		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) {
				dfs(nx, ny);
			}
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	vector<int>q;
	int x1, y1, x2, y2;
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> x1 >> y1 >> x2 >> y2;

		for (int i = x1; i < x2; i++) {
			for (int j = y1; j < y2; j++) {
				map[j][i] = 1;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				cnt = 0;
				dfs(i, j);
				q.push_back(cnt);
			}
		}
	}
	sort(q.begin(), q.end());

	cout << q.size() << '\n';

	for (int i = 0; i < q.size(); i++) cout << q[i] << " ";
	return 0;

}