[백준알고리즘] 2583번 영역 구하기

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

좌표로 배열의 영역 표시하는 방법

ex) 0 2 4 4 일 때,

(1,0)	(1,1)	(1,2)	(1,3)
(2,0)	(2,1)	(2,2)	(2,3)

for(i = 1; i < 3; i++)  ==>  for(i = M-4; i < M-2; i++)

for(j = 0; j < 4; j++)  ==> for(j = 0; j < 4; j++)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int M, N;
int map[101][101];
int group[101][101];
 
vector<int> v;
 
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
 
int cnt = 0;
 
void dfs(int x, int y)
{
    group[x][y] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int mx = x + dx[i];
        int my = y + dy[i];
 
        if (mx >= 0 & mx < M && my >= 0 && my < N && !map[mx][my] && !group[mx][my])
        {
            dfs(mx,my);
            cnt++;
        }
    }
    return;
}
 
int main(void)
{
    int K;
 
    int li, lj, ri, rj;
 
    cin >> M >> N >> K;
 
    for (int i = 0; i < K; i++)
    {
        cin >> li >> lj >> ri >> rj;
 
        // 좌표로 배열의 공간 표시하기
        for (int m = M - rj; m < M - lj; m++)
        {
            for (int n = li; n < ri; n++)
            {
                map[m][n] = 1;
            }
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // map이 직사각형에 가려져 있지 않고 grouping이 되어있지 않은 경우 dfs
            if(!map[i][j] && !group[i][j])
            {
                cnt = 1;
                dfs(i, j);
 
                v.push_back(cnt);
 
            }
        }
    }
    int num = v.size();
    cout << num << '\n';
 
    sort(v.begin(), v.end());
 
    for(int i = 0; i < num; i++)
    cout << v[i] << ' ';
 
    return 0;
}