백준 2583번 : 영역 구하기 - BFS 너비 우선 탐색 문제 C++

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

2583번: 영역 구하기

 

 

 

1. 문제설명

 

2583번 문제

2583번 문제

모눈 종이에 직사각형이 그려져 있을 때

직사각형이 색칠되어 있지 않은 남은 부분들의 갯수와 부분들의 넓이를 구해서

오름차순으로 정렬해 출력하면 된다.

사각형의 갯수가 곧 넓이가 된다.

 

 

 

 

 

2. 접근방법[알고리즘]

색칠된 부분을 저장하기 위해 M*N 배열을 만들어야한다.

좌표를 설정하는 걸 조심해야한다.

 

2583번 좌표설정

N, M은 7,5지만 이건 꼭짓점이고 실제로

해당 칸 마다 좌표를 부여하면 (0,0) ~ (6,4)까지만 사용 한다.

 

 

입력

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

arr[i][j]의 값에 색칠되었다면 -1을 저장하고 색칠되지 않았다면 0을 저장해준다.

색칠해줄 때도 (0,2)에서 (4,4)까지 칠해주는게 아니라 (0,2)에서 (3,3)까지 칠해주어야한다.

이유는 위와 동일하게 (4,4)는 사각형의 해당 좌표가아니라 꼭짓점이기 때문이다.

 

	//직사각형 -1로 칠하기
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = y1; j < y2; j++) { // y1 ~ <y2 까지 돌아야 한다
			for (int k = x1; k < x2; k++) { // x1 ~ <x2 까지 돌아야 한다
				arr[j][k] = -1;
			}
		}
	}

 

 

 

 

그리고 arr배열 값이 -1인 좌표는 BFS를 돌지 않고

arr배열이 0인 값만 탐색한다.

 

이제 arr배열을 돌면서 값이 0인 좌표를 발견하면

BFS를 실행하면서 arr 값에 사각형의 개수를 저장해준다.

 

2583번 문제

BFS 실행 코드

arr값이 0인 좌표를 발견할 때 arr 값을 1로 저장해준다. 

cnt 변수는 arr값이 0인 좌표를 발견했을 때 +1 해주어 전체 하얀 부분의 개수를 구할 수 있다.

this_area 변수는 BFS를 돌면서 0인좌표를 발견할 때마다 +1 해주어 해당 부분의 넓이를 저장해준다

그리고 Q가 empty가 되어 BFS가 끝나면 해당 하얀 부분을 다 탐색했다는 뜻이므로

this_area 변수의 값을 ans에 저장해준다.

 

이렇게 모든 좌표에대해 탐색하면 하얀 부분의 넓이를 모두 구할 수 있다.

	queue<pair<int, int> > Q;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				cnt++;
				arr[i][j] = 1;
				int this_area = 1;
				Q.push(make_pair(i, j));

				while (!Q.empty()) {
					int cur_x = Q.front().first;
					int cur_y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = cur_x + dx[k];
						int ny = cur_y + dy[k];
						if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
						if (arr[nx][ny] == 0) {
							arr[nx][ny] = ++this_area;
							Q.push({ nx,ny });
						}
					}
				}
				ans.push_back(this_area);
			}
		}
	}

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n,m,k, cnt, arr[101][101];
vector<int> ans;

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

	//색칠영역 -1로 두고
	//-1이 아닌 곳 BFS 돌면서 넓이 구해주면 된다
	cin >> m >> n >> k;

	//직사각형 -1로 칠하기
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = y1; j < y2; j++) {
			for (int k = x1; k < x2; k++) {
				arr[j][k] = -1;
			}
		}
	}

	//직사각형 확인
	//cout << "------------------------\n";
	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << arr[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	//cout << "-------------------\n";

	queue<pair<int, int> > Q;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				cnt++;
				arr[i][j] = 1;
				int this_area = 1;
				Q.push(make_pair(i, j));

				while (!Q.empty()) {
					int cur_x = Q.front().first;
					int cur_y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = cur_x + dx[k];
						int ny = cur_y + dy[k];
						if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
						if (arr[nx][ny] == 0) {
							arr[nx][ny] = ++this_area;
							Q.push({ nx,ny });
						}
					}
				}
				ans.push_back(this_area);
			}
		}
	}


	//결과 확인
	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << arr[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	//cout << "-------------------\n";


	//정답 출력
	cout << cnt << '\n';
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}

}

백준 2583 시간, 메모리

일반적인 BFS탐색 문제와 비슷하다.

 

다만 좌표설정하는 부분을 잘 유의해야할 필요가 있다.