백준 문제 2583번 영역 구하기 문제풀이 c++

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

2583번: 영역 구하기

 

문제해석

 

문제에 나온 설명처럼 빗금이 없는 부분의 영역을 구하여 오름 차 순으로 출력하면되는데

 

빗금이 있는곳을 1 없는곳을 0으로 세팅한 후

dfs또는 bfs를 사용하여 각 영역의 넓이를 오름차순으로 출력하여 풀었다.

 

문제에선 좌표로 x,y좌표로 나타나있는데 배열로 풀 경우 행 열로 표현이 편하기 때문에 뒤집어 풀었다.

무슨 말이냐면

윗 그림과 아래 그림은 동치인데 편의상 아래처럼 생각하여 풀었다는 뜻 어차피 이렇게 놓고 풀어도 답이 1 7 13임에는 변함이 없기 때문이고 코드 작성이 더 편하기 때문이다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue < int, vector<int>, greater<int> > pq;
void dfs(int cy,int cx);
bool inside(int ny,int nx);
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int a[101][101];
int m,n,k,cnt;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>m>>n>>k;
    for(int i=0; i<k; i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int j=y1; j<y2; j++)
        {
            for(int k=x1; k<x2; k++)
            {
                a[j][k]=1;
            }
        }
    }
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(a[i][j]==0)
            {
                cnt=0;
                dfs(i,j);
                pq.push(cnt);
            }
        }
    }
    cout<<pq.size()<<"\n";
    while(!pq.empty())
    {
        cout<<pq.top()<<" ";
        pq.pop();
    }
}
void dfs(int cy,int cx){
    a[cy][cx]=1;
    cnt++;
    for(int i=0; i<4; i++)
    {
        int ny=cy+dy[i];
        int nx=cx+dx[i];
        if(inside(ny,nx)&&a[ny][nx]==0)
        {
            dfs(ny,nx);
        }
    }
}

bool inside(int ny,int nx){
    if(0<=ny&&ny<m&&0<=nx&&nx<n)
    {
        return true;
    }
    else
    {
        return false;
    }
}