백준 2583. 영역 구하기

백준 2583. 영역 구하기

영역의 개수와 크기를 구하는 문제

1. 간단 설명

---

M * N 짜리 맵에

K의 사각형을 찍찍 긋는다

사각형을 여러개 그렸을 때,

나눠진 공간의 개수와 그 공간의 크기를 각각 구하는 문제

2. 예제

---

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

5 * 7 짜리 맵에 사각형 3개를 그린다

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

좌표계를 수정해서 왼쪽 위가 (0,0), 오른쪽 아래가 (N-1,M-1)이라고 하면

P1 = (X = 0, Y = 2), P2 = (X = 4, Y = 4)

첫번째 사각형을 그리면

0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 1 1 1 0 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 0

다음과 같이 그려진다

이와 같이 두번째, 세번째 사각형도 잘 그리면

0 0 0 0 3 3 0
0 2 0 0 3 3 0
1 2 1 1 0 0 0
1 2 1 1 0 0 0
0 2 0 0 0 0 0

다음과 같이 완성된다

여기서 0의 구역은 총 3개이고, 각각 7, 1, 13의 크기를 가지므로

3\n 1 7 13 을 출력하면 된다

3. 알고리즘

---

1. M, N, K 를 입력받는다
2. K개의 사각형을 입력받아, 그 범위를 칠한다
	2-1. 왼쪽 아래 좌표의 X,Y를 입력받는다
	2-2. 오른쪽 위의 좌표 X,Y를 입력받는다
	2-3. 해당 범위를 모두 1로 칠한다
3. 빈칸을 찾는다
	3-1. 2중 for문을 이용해 빈칸을 찾는다
		3-2-1. 빈칸이라면 현재 칸을 방문처리 후, 전체 구역 개수를 1 증가시킨다
		3-2-2. 이후 이 칸과 연결된 칸을 찾는다
4. 전체 구역 개수를 출력 후, 각 크기를 출력한다

4. 소스코드

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[101][101];
int M, N, K;
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
vector<int> res;

int BFS(int yy, int xx, int num) {
	
	int size = 0;
	queue< pair<int, int> > qu;
	qu.push({ yy, xx });
	map[yy][xx] = num;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();
		size++;

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;

			if (dy < 0 || dx < 0 || dy >= M || dx >= N) continue;
			if (map[dy][dx] != 0) continue; // 벽이거나 이미 처리한 경우

			map[dy][dx] = num;
			qu.push({ dy,dx });
		}
	}

	return size;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> M >> N >> K;
	
	// 직사각형 K개 그리기
	for (int i = 0; i < K; i++) {
		int BL_x, BL_y, TR_x, TR_y;
		cin >> BL_x >> BL_y >> TR_x >> TR_y;

		// (BL_x, BL_y), (TR_x, TR_y) 순서로 주어짐
		for (int yy = BL_y; yy < TR_y; yy++) {
			for (int xx = BL_x; xx < TR_x; xx++) {
				map[yy][xx] = 1; 
			}
		}
	}
	
	// BFS 구역 개수, 크기 세기
	int total = 0;
	for (int y = 0; y < M; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0) {
				res.push_back(BFS(y, x, ++total));
			}
		}
	}

	// 결과 출력
	sort(res.begin(), res.end());

	cout << total << '\n';
	for (int e : res) {
		cout << e << " ";
	}

	return 0;
}