[백준/BOJ] 2583번 영역 구하기 (C++)

www.acmicpc.net/problem/2583

2583번: 영역 구하기

BFS의 유형의 문제입니다.

(0, 0)이 왼쪽 아래부터 시작이라는 것에 주의해야합니다. 2차원 배열을 사용해야하므로 (0, 0)을 왼쪽 위에 두고 문제를 풀어야합니다. 그 이후에는 전형적인 BFS 문제입니다.

 

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

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

int BFS(int sx, int sy) {
	int size = 1;
	queue<pair<int, int > > q;
	q.push({ sx, sy });
	map[sx][sy] = 1;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = 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 || nx >= m || ny < 0 || ny >= n || map[nx][ny] == 1) continue;
			q.push({ nx, ny }); 
			map[nx][ny] = 1;
			size++;
		}
	}
	
	return size;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int answer = 0;
    vector<int> v;
    
    cin >> m >> n >> k;
    for(int i = 0; i < k; i++) {
    	int x1, y1, x2, y2;
    	cin >> x1 >> y1 >> x2 >> y2;
    	for(int a = y2 - 1; a >= y1; a--) {
    		for(int b = x2 - 1; b >= x1; b--) {
    			map[a][b] = 1;
			}
		}
	}
	
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			if(map[i][j] == 0) {
				answer++;
				v.push_back(BFS(i, j));
			}
		}
	}
	
	sort(v.begin(), v.end());
	cout << answer << "\n";
	for(int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}