백준 2583: 영역 구하기

문제 요약

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

왼쪽 아래의 x,y와 오른쪽 위의 x,y를 입력 받으면, 그 사이의 배열값을 모두 1로 만들고,

0이 들어가 있는 부분을 DFS로 탐색했다.

DFS내에서 연결된 요소의 개수는 cnt로 카운트하여 벡터에 넣어주고, 벡터를 sort()로 정렬한 뒤, 출력은 벡터의 size()와 반복자를 이용하여 출력했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool visited[100][100];
int map[100][100];
int cnt, m, n;

void dfs(int i, int j) {
	cnt++;
	visited[i][j] = true;
	if (i < m - 1)
		if (!map[i + 1][j] && !visited[i + 1][j]) dfs(i + 1, j);
	if (i > 0)
		if (!map[i - 1][j] && !visited[i - 1][j]) dfs(i - 1, j);
	if (j < n - 1)
		if (!map[i][j + 1] && !visited[i][j + 1]) dfs(i, j + 1);
	if (j > 0)
		if (!map[i][j - 1] && !visited[i][j - 1]) dfs(i, j - 1);
}

int main()
{
	int k, ary[4];
	string in;
	vector<int> res;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < 4; j++) scanf("%d", ary + j);
		for (int j = ary[1]; j < ary[3]; j++) {
			for (int l = ary[0]; l < ary[2]; l++)
				map[j][l] = 1;
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				if (!map[i][j]) {
					cnt = 0;
					dfs(i, j);
					res.push_back(cnt);
				}
				else visited[i][j] = true;
			}
		}
	}
	printf("%d\n", res.size());
	sort(res.begin(), res.end());
	for (auto& it : res)
		printf("%d ", it);
	return 0;
}