[C++] 2583 : 영역 구하기

실버 Ⅰ

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int m, n, k;
vector <int> area;
int ar = 0;
int cnt = 0;
int map[100][100] = { 0, };

void dfs(int a, int b) {
	if (map[a][b] == 1 || a < 0 || a >= m || b < 0 || b >= n) return;

	map[a][b] = 1;
	ar++;

	dfs(a - 1, b);
	dfs(a + 1, b);
	dfs(a, b - 1);
	dfs(a, b + 1);
}


int main() {

	scanf("%d%d%d", &m, &n, &k);

	int x1, y1, x2, y2;
	for (int i = 0; i < k; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		for (int y = y1; y < y2; y++)
			for (int x = x1; x < x2; x++) map[y][x] = 1;

	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				ar = 0;
				dfs(i, j);
				cnt++;
				area.push_back(ar);
			}
		}
	}
	
	sort(area.begin(), area.end());

	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) printf("%d ", area.at(i));
}

dfs나 bfs 둘 다 풀 수 있을 것 같은 문제

나는 dfs로 풀었다

 

bfs로 풀면 영역의 크기를 구하는 부분을 수정해야 될 것 같다

그래도 위의 코드에서 영역의 크기를 구한 로직이

방문함 -> 영역 크기++(초기값 0)  해줌 이니까

이것만 제대로 생각하고 있으면 어렵지 않게 할 수 있을 것 같다

 

그래도 나는 bfs 문제 많이 안 풀어봤으니까

이것도 bfs로 풀어보긴 해야 할 듯