[백준 BOJ][C++]2583번 영역 구하기 풀이: DFS/BFS

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

2583번: 영역 구하기

 

 

이 문제는 재귀호출을 통한 DFS로 해결할 수 있습니다. 

 

먼저 N*M 크기의 지도의 모든 위치에 해당하는 값을 0으로 set 해줍니다. 

 

 K개의 직사각형에 대한 위치 정보가 주어지면 직사각형에 해당하는 위치를 지도에서 1로 set 해줍니다.

 

 이제 아직 방문하지 않은 영역에서 dfs()를 호출합니다. 이때 영역의 넓이도 구해야하므로 dfs()를 호출하기 전 ret을 0으로 set한 뒤 dfs() 내부에서 ret++를 해줍니다. 

 

 dfs()는 해당 위치에서 연결된 모든 영역을 탐색하며 ret은 그 영역의 개수를 나타냅니다. 

 

 dfs()가 종료되면 분리된 영역의 개수를 나타내는 cnt를 cnt++ 해줍니다. 

 

 이때, 분리된 영역의 넓이 ret을 오름차순으로 정렬하여 출력해야하기 때문에 ret을 우선순위큐에 push해줍니다. 

 

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

using namespace std;

int n, m, k;
int map[101][101] = { 0, };
bool visit[101][101] = { false, };
int ret = 0;

int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };

void dfs(int x, int y) {

	visit[y][x] = true;
	ret++;

	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0 || tx >= n || ty < 0 || ty >= m)
			continue;
		if (visit[ty][tx] || map[ty][tx] == 1)
			continue;

		dfs(tx, ty);
	}
}

int main(void) {

	int cnt = 0;
	int x1, x2, y1, y2;
	priority_queue<int, vector<int>, greater<int>> ans;

	cin >> m >> n >> k;

	while (k > 0) {

		cin >> x1 >> y1 >> x2 >> y2;

		for (int i = y1; i < y2; i++) {
			for (int j = x1; j < x2; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
				}
			}
		}

		k--;
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j] && map[i][j] == 0) {
				ret = 0;
				dfs(j, i);
				cnt++;
				ans.push(ret);
			}
		}
	}

	cout << cnt << endl;
	while (!ans.empty()) {
		cout << ans.top() << " ";
		ans.pop();
	}

	return 0;
}