백준 2583번 : 영역 구하기 [C++]

 

 

 

 

 

DFS를 사용해서 풀었다.

빈칸의 넓이는 빈칸의 개수와 같으므로 cnt로 ++하면서 vector에 넣었다. 

 

 

 

#include <iostream>
#include <cstring> //memset
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100;

typedef struct {
	int y, x;
}dir;

dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };


int N, M, K;
int graph[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> q;
int result, cnt;
vector<int> each;


void BFS(int y, int x) {
	q.push(make_pair(y, x));
	visited[y][x] = true;
	cnt++;
	
	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = y + moveDir[i].y;
			int nextX = x + moveDir[i].x;

			if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
				if (graph[nextY][nextX] == 0 && !visited[nextY][nextX]) {
					visited[nextY][nextX] = true;
					q.push(make_pair(nextY, nextX));
					cnt++;
				}
			}
		}
	}
}

int main(void) {

	cin >> N >> M >> K;

	for (int k = 0; k < K; k++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		for (int i = b; i < d; i++) {
			for (int j = a; j < c; j++) {
				graph[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 0 && !visited[i][j]) {
				cnt = 0;
				BFS(i, j);
				result++;
				each.push_back(cnt);
			}
		}
	}


	sort(each.begin(), each.end());
	cout << result << endl;
	for (int i = 0; i < each.size(); i++) {
		cout << each[i] << " ";
	}
	cout << endl;

	return 0;
}