백준 2583번 - 영역 구하기

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

색칠된 영역을 표시할 때 4개의 꼭짓점 중에 기준점을 잡아야 한다.
나는 4개의 꼭짓점 중에서 왼쪽 아래를 기준으로 해당 좌표가 색칠됐을 경우 0에서 1씩 더해주는 방식으로 접근하였다.


영역의 개수는 main 함수에서 dfs를 호출할 때마다 더해주는 방식으로 구할 수 있다.
그리고 색칠되지 않은 넓이는 사각형이 몇개인지 구하면 된다. 

왜냐하면 정사각형이기 때문에 하나의 사각형이 추가될 때마다 넓이가 1씩 추가되기 때문이다.


그리고 마지막으로 넓이가 저장된 배열을 오름차순으로 정렬해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int M,N,K;
int arr[100][100]={0};
int visited[100][100]={0};
 
int dfs(int y,int x){
    
    int cnt=1;
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=M || nx<0 || nx>=N)
            continue;
        
        if(arr[ny][nx] || visited[ny][nx])
            continue;
        
        visited[ny][nx]++;
        cnt+=dfs(ny,nx);
    }
    
    return cnt;
}
 
int main(){
    
    cin>>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 x=x1;x<x2;x++)
            for(int y=y1;y<y2;y++)
                arr[y][x]++;
        
    }
    
    vector<int> ans;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(!arr[i][j] && !visited[i][j]){
                visited[i][j]++;
                ans.push_back(dfs(i,j));
            }
        }
    }
    
    cout<<ans.size()<<endl;
    
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
 
    return 0;
}