BOJ 2583 : 영역 구하기

BOJ 2583

[BOJ 2583(S1) 리뷰]

 

첨엔 문제 읽고 이해가 안되서 멍때렸다.

천천히 읽어보니 M*N의 직사각형에 K개의 직사각형이 주어지고 그 직사각형을 제외한 영역이 몇개로 나뉘며 나뉜 영역들의 넓이는 몇인지 구하는 문제이다.

 

입력값이 2 0 4 4 이런식으로 입력이 들어오면 (2,0)부터 (4,4)까지가 직사각형의 영역이다. 이 점이 좀 헷갈렸지만 이중for문을 통하여 직사각형 영역을 색칠했고 나머지 영역에 대해 BFS를 수행했다. 직사각형 영역을 색칠하는것까지만 하면 나머진 전형적인 BFS이므로 쉽게 해결할 수 있다. 

 

각 영역들의 넓이를 오름차순으로 출력하라 했기에 그냥 우선순위큐를 사용했다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

int board[101][101];
int check[101][101];
priority_queue <int, vector<int>, greater<int>> result;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int m, n, k;
	cin >> m >> n >> k;

	
	int input[4]; // 0 2 4 4 입력받으면 (2,0) , (4,4) 이런식으로 생각하기.
	while (k--)
	{
		for (int i = 0; i < 4; i++)
			cin >> input[i];

		for (int i = input[1]; i < input[3]; i++)
		{
			for (int j = input[0]; j < input[2]; j++)
			{
				board[i][j] = 1;
				check[i][j] = 1;
			}
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[i][j] != 0) continue;
			int area = 0;
			queue <pair<int, int>> Q;
			check[i][j] = 1;
			Q.push({ i,j });
			cnt++;
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				area++;
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];
					if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
					if (board[nx][ny] != 0 || check[nx][ny] != 0) continue;
					check[nx][ny] = 1;
					Q.push({ nx,ny });
				}
			}
			result.push(area);
		}
	}


	cout << cnt << '\n';
	int size = result.size();
	while (!result.empty())
	{
		cout << result.top() << ' ';
		result.pop();
	}

}