[백준] 2583번 영역 구하기

문제 링크

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

2583번: 영역 구하기

전형적인 탐색 문제다. bfs를 해도 되고 dfs를 해도 상관 없다. 필자 같은 경우는 dfs가 좀 더 편하기 때문에 dfs로 코드를 작성하였다. 급하게 풀어서 변수명들이 개판인 것 같다. 앞으로는 좀 더 신경써서 변수명을 정해야겠다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int M,N,K;
int wholemap[100][100] = { 0, };
int result_count = 0;
vector<int> result_pi;
 
int temp_area = 0;
int dfs(int x,int y)
{
    temp_area += 1;
    wholemap[x][y] = 1;
 
    if (wholemap[x + 1][y] == 0 && ((x + 1) <N))
    {
        dfs(x + 1, y);
    }
    if (wholemap[x ][y+1] == 0 && ((y + 1) < M))
    {
        dfs(x , y+1);
    }
    if (wholemap[x][y - 1] == 0 && ((y - 1) > -1))
    {
        dfs(x, y - 1);
    }
    if (wholemap[x-1][y ] == 0 && ((x - 1) > -1))
    {
        dfs(x-1, y );
    }
 
    return temp_area;
 
}
 
int main() {
 
    cin >> M >> N >> K;
 
    int tempquad[4];
 
    for (int i = 0; i < K; i++)
    {
        cin >> tempquad[0] >> tempquad[1] >> tempquad[2] >> tempquad[3];
    
        for (int x = tempquad[0]; x < tempquad[2]; x++)
        {
            for (int y = tempquad[1]; y < tempquad[3]; y++)
            {
                wholemap[x][y] += 1;
            }
        }
    }
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (wholemap[i][j] == 0)
            {
                temp_area = 0;
                result_pi.push_back(dfs(i, j));    
            }
        }
    }
 
    result_count = result_pi.size();
    sort(result_pi.begin(), result_pi.end());
    cout << result_count << endl;
    for (auto i : result_pi)
    {
        cout << i << " ";
    }
 
    return 0;
}