시작

이 문제는 연결된 컴포넌트와 그 노드의 개수를 구하는 문제다. 그렇다면 어떤 알고리즘을 사용하는게 좋냐고 이야기 하면, 그건 바로 DFS를 이용하여 푸는게 가장 이상적인 문제다. 그렇다면 한번 알고리즘을 작성을 해보자 그전엔 예외 사항 부터 작성을 해보자면

예외사항

1, 방문했으면 안됨
2. 만약 그 칸이 지나가지 못하는 칸이면 넘기기

이런 간단한 예외사항을 가지고 한번 알고리즘을 작성을 시작해보자. 우선 이문제는 DFS를 이용한다는 것을 알아야된다

알고리즘

1. 만약 방문했다면 넘기기
2. 만약 count범위가 벗어나면 push_back
3. 만약 범위를 벗어난다면 넘기기

여기서 count가 뭔지 궁금할텐데, count는 빈 공간을 나타내기도 하지만, 이는 내가 있는 노드의 개수를 구하기 위해서 사용되는 변수다. 그렇다면 한번 이 알고리즘을 가지고 코드를 짜보자

코드

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
#include<tuple>

using namespace std;

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int N, M, K, conting = 0;
vector<int> countV(1);
vector<vector<int>> _map;
vector<vector<int>> visited;

void DFS(int x, int y) {
	// 방문했거나 지나가지 못하면 넘기기
	if (_map[y][x] == 1 || visited[y][x] == 1) return;
	visited[y][x] = 1;
	// 만약 count범위가 벗어나면 push back
	if (countV.size() <= conting) countV.push_back(1);
	else {
		countV[conting]++;
	}

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 범위가 넘어가면 넘기기
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		// 재귀 호출
		DFS(nx, ny);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> M >> N >> K;
	_map.resize(M);
	visited.resize(M);
	for (int i = 0; i < M; i++) {
		_map[i].resize(N);
		visited[i].resize(N);
	}

	for (int i = 0; i < K; i++) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1;
		cin >> x2 >> y2;
		for (int j = y1; j < y2; j++) {
			for (int k = x1; k < x2; k++) {
				_map[j][k] = 1;
			}
		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			// 만약 들어가지 못하는 칸이거나 방문했던 칸이면 넘기기
			if (_map[i][j] == 1 || visited[i][j] == 1) continue;
			conting++;
			DFS(j, i);
		}
	}

	// 정렬시켜서 올바르게 출력시키기
	sort(countV.begin(), countV.end());
	cout << conting << "\n";
	for (int i = 1; i < countV.size(); i++) {
		cout << countV[i] << " ";
	}
}