[백준/BOJ] 백준 2583번 : 영역 구하기

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

2583번: 영역 구하기

입력받은 직사각형들로 board를 덮고, 덮이지 않은 영역을 발견했을 때 그 영역의 넓이를 구했다. 해당 영역의 넓이를 구하는 방법은 해당 영역의 한 점에서 bfs를 하였고, 한 칸의 넓이가 1이라는 것을 이용해 해당 영역의 칸 수를 셌다.

 

코드

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

int m, n, k;
int board[100][100];
int discoverd[100][100];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//직사각형으로 모눈종이를 덮는다
void boxCover(vector<pair<pair<int, int>, pair<int, int>>> box_list)
{
	for (int i = 0; i < box_list.size(); i++)
	{
		pair<pair<int, int>, pair<int, int>> box = box_list[i];

		for (int i = box.second.first; i < box.first.first; i++)
			for (int j = box.first.second; j < box.second.second; j++)
				board[i][j] = 1;
	}
}

//(x,y)가 속한 영역의 넓이를 구한다
int Solve(int x, int y)
{
	queue<pair<int, int>> q;
	int ret = 0;

	//발견을 표시하고 큐에 넣는다
	discoverd[x][y] = 1;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		pair<int,int> here = q.front();
		q.pop();
		ret++;//현재 위치 크기

		//범위를 넘어가지 않고, 발견된적이 없고, 직사각형으로 덮이지 않았을때
		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
			if (there.first >= 0 && there.first < m && there.second >= 0 && there.second < n && discoverd[there.first][there.second] == 0 && board[there.first][there.second] == 0)
			{
				discoverd[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int x1, y1, x2, y2;
	vector<pair<pair<int, int>, pair<int, int>>> box_list;
	int num = 0;
	vector<int> area;
	int temp_area;

	memset(board, 0, sizeof(board));
	memset(discoverd, 0, sizeof(discoverd));

	cin >> m >> n >> k;

	for (int i = 0; i < k; i++)
	{
		//모눈종이가 왼쪽 아래가 (m,0),오른쪽 위가(0,n)형태라고 만들고
		//거기에 맞게 직사각형 표현을 바꾼다
		cin >> x1 >> y1 >> x2 >> y2;
		pair<int, int> xy1 = make_pair(m-y1, x1);
		pair<int, int> xy2 = make_pair(m-y2, x2);

		box_list.push_back(make_pair(xy1, xy2));
	}

	//입력받은 직사각형으로 모눈종이를 덮는다
	boxCover(box_list);

	for(int i=0; i<m; i++)
		for (int j = 0; j < n; j++)
		{
			//영역을 하나 발견했을때
			if (discoverd[i][j] == 0 && board[i][j] == 0)
			{
				num++;
				area.push_back(Solve(i, j));
			}
		}

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

	cout << num << "\n";

	for (int i = 0; i < area.size(); i++)
	{
		cout << area[i] << " ";
	}

	return 0;
}