[BOJ 2583] 영역 구하기

출처 : https://www.acmicpc.net/problem/2583

1. 입력을 받아 바로 배열에 표시를 한다.

2. 비어있는 부분을 dfs를 돈다.

3. 총 dfs를 시작한 개수와 넓이를 저장하여 출력한다.

#include <iostream>

#include <algorithm>

using namespace std;

int M, N, K, cnt;

int map[100][100];

bool visited[100][100];

int result[10000];

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

void dfs(int i, int j)

{

visited[i][j] = true; cnt++;

for (int d = 0; d < 4; d++)

{

int nexti = i + dir[d][0]; int nextj = j + dir[d][1];

if (nexti >= 0 && nextj >= 0 && nexti < M && nextj < N

&& map[nexti][nextj] == 0 && !visited[nexti][nextj]) dfs(nexti, nextj);

}

}

int main()

{

cin >> M >> N >> K; cnt = 0; int z = 0;

for (int i = 0; i < K; i++)

{

int yy1, xx1, yy2, xx2;

cin >> xx1 >> yy1 >> xx2 >> yy2;

for (int i = yy1;i < yy2;i++) for (int j = xx1;j < xx2;j++) map[i][j] = 1;

}

for (int i = 0; i < M;i++)

{

for (int j = 0; j < N; j++)

{

if (map[i][j] == 0 && !visited[i][j])

{

dfs(i, j);

result[z] = cnt;

cnt = 0; z++;

}

}

}

sort(result, result + (++z));

cout << z << endl;

for (int i = 1; i < z; i++)

{

cout << result[i] << " ";

}

return 0;

}