[BOJ] 영역 구하기_2583 C++ 풀이

문제

눈금의 간격이 1인 MxN(M,N ≤ 100) 크기의 모눈종이에 k개의 직사각형을 그릴 때, 이 직사각형을 제외한 나머지 부분이 총 몇개인지 출력하고 각 나머지 부분의 넓이를 출력하는 문제 이다.

접근 방법

모눈종이 한칸을 하나의 노드로 생각하고 입력받은 직사각형을 이미 방문한 노드로 처리하여 깊이 우선 탐색을 수행 했다. 분리된 나머지 부분의 넓이와 개수를 출력하는 것이므로 연결 요소 개념으로 생각 하였고 $($연결 요소의 개수 == 분리된 나머지 부분의 개수) 탐색할 상하좌우 방향은 구조체를 사용하여 구현하였다.

구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct
{
    int x,y;
} D;

int area[101][101]={0,};
int a;
D dir[4] = { {-1,0}, {0,-1}, {1,0}, {0,1} };
int m,n;

void dfs(int r, int c)
{
    if(area[r][c]==0)
    {
        a++;
        area[r][c]=1;
        for(int i=0; i<4; i++)
        {
            int X=dir[i].x+r;
            int Y=dir[i].y+c;
            if(0<=X && X<m && 0<=Y && Y<n)
            {
                dfs(X,Y);
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int k;
    int x1, x2, y1, y2;
    vector<int> total;
    cin>>m>>n>>k;

    for(int i=0; i<k; i++)
    {
        cin>>x1>>y1>>x2>>y2;

        for(int col=x1; col<x2; col++)
        {
            for(int row=y1; row<y2; row++)
            {
                area[row][col]=1;
            }
        }
    }

    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(area[i][j]==0)
            {
                a=0;
                dfs(i,j);
                total.push_back(a);
            }
        }
    }
    sort(total.begin(), total.end());
    cout<<total.size()<<'\n';
    for(int i=0; i<total.size(); i++) cout<<total[i]<<' ';
    return 0;
}

BOJ_영역 구하기