백준2583 영역 구하기

작성일 | In

문제 링크

  • http://icpc.me/2583

문제 출처

  • 2006 지역 본선 고등2

사용 알고리즘

  • DFS/BFS

시간복잡도

  • O(n2)

풀이

이 문제는 전형적인 DFS/BFS 문제입니다.

n, m이 모두 100 이하의 자연수이기 때문에 이차원 배열을 이용애 100*100 격자를 만들어줍니다.
직사각형이 있는 자리는 1, 없는 자리는 0으로 표현한 뒤, DFS나 BFS를 돌리면서 연결 요소의 개수를 구해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int map[100][100];
vector<int> ans;
int n, m, k, sum;
int di[] = {0, 0, 1, -1};
int dj[] = {1, -1, 0, 0};

void dfs(int i, int j){
	if(map[i][j]) return;
	if(i < 0 || i >= n || j < 0 || j >= m) return;
	map[i][j] = 2;
	sum++;
    for(int k=0; k<4; k++){
        dfs(i+di[k], j+dj[k]);
    }
}

int main(){
	scanf("%d %d %d", &n, &m, &k);
	for (int i=0; i<k; i++){
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		for (int j=b; j<d; j++){
			for (int z=a; z<c; z++)
				map[j][z] = 1;
		}
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(!map[i][j]){
				sum = 0;
				dfs(i, j);
				ans.push_back(sum);
			}
		}
	}
	printf("%d\n", ans.size());
	sort(ans.begin(), ans.end());
	for(int i : ans) printf("%d ", i);
}