[bfs] 백준 2583 영역 구하기

하용권 2019. 4. 29. 20:14

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

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

www.acmicpc.net

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

int main(){
	int map[100][100] = { 0 };
	int m, n, k;
	int cnt = 0;
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	vector<int> ret;
	bool visited[100][100] = { 0 };
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++){
		int r_x, r_y, l_x, l_y;
		cin >> l_x >> l_y >> r_x >> r_y;
		l_y = m-1 - l_y;
		r_y = m-1 - r_y;
		for (int j = l_y; j > r_y; j--){
			for (int k = l_x; k < r_x; k++){
				map[j][k] = 1;
			}
		}
	}

	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			queue<pair<int, int>> q;
			int tmp_ret = 0;
			if (visited[i][j] || map[i][j]) continue;
			cnt += 1;
			q.push({ i, j }); visited[i][j] = true;


			while (!q.empty()){
				tmp_ret += 1;
				int x = q.front().second, y = q.front().first;
				q.pop();

				for (int k = 0; k < 4; k++){
					int xx = x + dx[k], yy = y + dy[k];

					if (xx >= n || yy >= m || xx < 0 || yy < 0) continue;
					if (map[yy][xx] == 1 ||visited[yy][xx]) continue;
					q.push({ yy, xx }); visited[yy][xx] = 1;
				}
			}

			ret.push_back(tmp_ret);
		}
	}

	sort(ret.begin(), ret.end());

	cout << cnt << endl;
	for (int i = 0; i < cnt; i++){
		cout << ret[i] << ' ';
	}

}