[백준] 2583번 영역 구하기

2583번: 영역 구하기

BFS로 풀었다.

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

int n;
vector<int> countAll;
vector<int> allArea;

int main() {
	int m, n, k;
	cin >> m >> n >> k;
	vector<vector<int>> v(m);
	for (int i = 0; i < m; i++) 
		v[i] = vector<int>(n);
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++) {
			for (int y = y1; y < y2; y++) {
				v[y][x] = 1;
			}
		}
	}
	vector<vector<bool>> visited(m);
	for (int i = 0; i < m; i++)
		visited[i] = vector<bool>(n);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] == 0 && !visited[i][j]) {
				queue < pair<int, int>> q;
				q.push(make_pair(i, j));
				int area = 0;
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					if (!visited[cur.first][cur.second] && v[cur.first][cur.second] == 0) {
						visited[cur.first][cur.second] = true;
						area++;
						if (cur.first + 1 < m && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 0) {
							q.push(make_pair(cur.first + 1, cur.second));
						}
						if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 0) {
							q.push(make_pair(cur.first - 1, cur.second));
						}
						if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 0) {
							q.push(make_pair(cur.first, cur.second + 1));
						}
						if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 0) {
							q.push(make_pair(cur.first, cur.second - 1));
						}
					}
				}
				allArea.push_back(area);
			}
		}
	}
	cout << allArea.size() << endl;
	sort(allArea.begin(), allArea.end());
	for (int i = 0; i < allArea.size(); i++) {
		cout << allArea[i] << " ";
	}
	return 0;
}