백준] 2583 - 영역 구하기(한국정보올림피아드 2006; KOI 2006)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

소스코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M, K;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
vector<vector<int> > area;
int BFS(int x, int y)
{
	int cnt = 0;
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	area[x][y] = -1;
	cnt++;
	while (!q.empty())
	{
		int cx = q.front().first, cy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dir[i][0], ny = cy + dir[i][1];
			if ((nx >= 0 && nx < N) && (ny >= 0 && ny < M) && area[nx][ny] == 0)
			{
				q.push(make_pair(nx, ny));
				cnt++;
				area[nx][ny] = -1;
			}
		}
	}
	return cnt;
}
int main(void)
{
	cin >> M >> N >> K;
	area = vector<vector<int> >(N, vector<int>(M, 0));
	
	int x1, y1, x2, y2;
	for (int i = 0; i < K; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++)
		{
			for (int y = y1; y < y2; y++)
			{
				area[x][y] = 1;
			}
		}
	}

	vector<int> sector;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (area[i][j] == 0)
			{
				sector.push_back(BFS(i, j));
			}
		}
	}
	sort(sector.begin(), sector.end());

	cout << sector.size() << '\n';
	for (vector<int>::iterator it=sector.begin();it!=sector.end();it++)
	{
		cout << *it << ' ';
	}
}

Tip

BFS, DFS 둘 중 아무거나 하나를 골라 풀면 된다. 문제에서 주어지는 좌표값을 바탕으로 배열에 직사각형들을 1로 매핑하고, 1이 아닌 값들을 찾아나가는 방식으로 풀면 된다.