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

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

2583번: 영역 구하기

 

M,N,K가 주어지고 K개의 직사각형이 주어질 때,

직사각형 부분을 제외한 나머지 영역들의 개수와 넓이를 구하는 문제이다.

 

왼쪽 아래부터 (0,0) 시작이라 좀 헷갈릴 수 있는데 개의치 않고 풀어도 상관없다.

 

어떻게 풀지 조금 생각하다가, 시작 점이 여러개인 BFS 풀듯이 직사각형이 아닌 모든 점을 시작점으로 생각하고, 방문한 정점은 바로 빼버리면 되겠다 싶어서 그렇게 풀기로 했다.

 

내가 생각한 로직은 다음과 같다.

1. 직사각형이 아닌 모든 점을 Main 큐에 push

2. Main 큐에서 정점 하나를 빼고, Main 큐에서 빠진 정점이 방문하지 않은 정점이면 그 정점을 가지고 BFS

3. BFS를 하는 동안 큐에 새로운 정점이 들어갈 때 마다 넓이 + 1

4. Sub 큐 반복문을 빠져나오면 한 영역의 계산이 끝났다는 뜻이므로 넓이를 저장하고 2번부터 다시 수행

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define MAX 105
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int m, n, k;
queue <pair<int, int>> Main, sub;
int board[MAX][MAX];
bool visited[MAX][MAX];
vector <int> res;
void input()
{
	int x1, y1, x2, y2;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++)
	{
		// x와 y좌표 반대로 쓰는거 조심하기
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = y1; i < y2; i++)
		{
			for (int j = x1; j < x2; j++)
				board[i][j] = 1;
		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{	// 미리 후보가 될 수 있는 시작점들을 넣어둠 (혹은 2중 for문으로 바로 넣고 돌려도 됨 -> 바킹독님 코드)
			if (board[i][j] == 0)
				Main.push({ i,j });
		}
	}

}
void solve()
{
	while (!Main.empty())
	{
		
		pair<int, int> t = Main.front(); Main.pop();
		//정점이 중복될 수 있으므로 방문하지 않은 정점만 처리
		if (!visited[t.X][t.Y])
		{
			visited[t.X][t.Y] = true;
			sub.push(t);
			int cnt = 1; // 1부터 시작하는 이유-> 이미 시작점을 방문하는 순간 넓이가 1임
			while (!sub.empty())
			{
				pair<int, int> cur = sub.front(); sub.pop();
			
				for (int dir = 0; dir < 4; dir++)
				{
					int tx = cur.X + dx[dir];
					int ty = cur.Y + dy[dir];
					if (tx < 0 || tx >= m || ty < 0 || ty >= n) continue;
					if (board[tx][ty] == 1 || visited[tx][ty] == true) continue;
					visited[tx][ty] = true;
					sub.push({ tx,ty });
					cnt++; // 조건이 맞았다면 넓이 1 증가시키기
					
				}

			}

			res.push_back(cnt); // sub가 끝났다는것은 영역 하나 처리가 끝났다는 것 -> 정답 추가
			
		}
	}
	
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	input();
	solve();
	cout << res.size() << "\n";
	sort(res.begin(), res.end());
	for (auto i : res)
		cout << i << ' ';
}