BOJ 2583 영역구하기

📎Problem Link

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

2583번: 영역 구하기

 

📋 문제 정리

• M X N크기의 모눈종이(M, N≤100)위의 K 개의 직사각형을 그림
• 직사각형으로 인해 분리된 영역들의 각 칸 수를 구하기
• 첫째 줄에는 M, N, K 입력 (이  때, M, N, K 모두 100 이하의 자연수)
• 둘째줄부터 K개의 줄에는 직사각형의 왼쪽 꼭짓점 x, y 좌표, 직사각형의 오른쪽 꼭짓점 x, y 좌표 입력
• 구한 칸 수들은 오름차순으로 정렬하여 출력할 것

📌 예제 1

 

사실 문제에서는 0,0이 왼쪽 아래, M, N이 오른쪽 위로 제시하고 있다. 그 사실을 문제를 거의 풀어갈 때 쯤에 알았지만, 문제를 풀어나가는데에 그 부분은 크게 결과를 좌지우지하지 않을 것 같아 나는 그대로 진행했다.

나는 문제와는 반대로 0,0을 왼쪽 위로 두고, M, N을 오른쪽 아래로 두었다. 그 결과 그림은 위와 같이 그려졌다.

---

💻 Code

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 100
using namespace std;
int move_x[4] = { 0, 0, 1, -1 };
int move_y[4] = { 1, -1, 0, 0 };

class Map {
public:
	int M, N, K;
	int map[MAX][MAX] = { 0 };
	queue <pair<int, int>> q;
	vector<int> notnemo;
	int count;
	
	void DFS(int y, int x) {
		q.push(make_pair(y, x));

		while (!q.empty()) {
			int cy = q.front().first;
			int cx = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cx + move_x[i];
				int ny = cy + move_y[i];

				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;

				if (!map[ny][nx])
				{
					q.push(make_pair(ny, nx));
					map[ny][nx] = 2;
					count++;
				}
			}
		}
	}
};

이번 queue 사용에서 달라진 점이 있다. 먼저 DFS함수는 x,y 좌표와 함께 호출되면서 시작한다. 이전에는 x,y좌표를 queue에 각각 넣었지만 이번에는 queue<pair<int, int>> q를 선언하여 x,y좌표를 쌍으로 넣었다. 이 좌표들은 위의 코드에서 볼 수 있는 것처럼 q.front().first, q.front().second를 이용하여 불러올 수 있다.

 

int main() {
	int block = 0;
	Map area;
	cin >> area.M >> area.N >> area.K;

	for (int i = 0; i < area.K; i++) {
		int left_x, left_y, right_x, right_y;
		cin >> left_x >> left_y >> right_x >> right_y;

		for (int j = left_y; j <= right_y - 1; j++) {
			for (int k = left_x; k <= right_x - 1; k++) {
				area.map[j][k] = 1;
			}
		}
	}

	for (int i = 0; i < area.M; i++) {
		for (int j = 0; j < area.N; j++) {
			if (area.map[i][j])
				continue;

			area.count = 1;
			area.map[i][j] = 2;
			area.DFS(i, j);
			area.notnemo.push_back(area.count);
		}
	}

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

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

DFS 함수와 main 문의 이중 for문에서 함께 볼 수 있듯이 방문한 좌표의 값은 2로 변경하여 방문했음을 표시했다.

---

이 문제를 수월하게 풀었지만 지금 블로그를 작성하며 리뷰하면서 반성한 점이 있다. 사실 백준에 제출할 때까지만 해도 함수의 이름은 BFS였고, BFS를 작성하겠다는 생각으로 코드를 작성했다. 그런데 지금 보니 이건 BFS를 가장한 DFS라는 생각이 든다. 일단 BFS와 DFS를 제대로 구분하기 위한 개념부터 정리를 해야겠다,,,,,