（매일 BOJ）C++ 2583번 영역 구하기

이번 문제는 2583번 영역 구하기다

문제 설명

• 크기가 M × N인 2차원 평면이 있고 이 평면에 직사각형 K개가 주어지며, 각 직사각형 영역은 색칠되어 있다고 가정합니다.
• 색칠된 부분을 제외한 나머지 빈 칸들이 몇 개의 분리된 영역을 이루는지, 그리고 각 영역의 넓이를 구하는 문제다

출력:

1. 영역의 개수
2. 각 영역의 넓이(오름차순)

접근법

1. 그래프 초기화
   • graph[y][x] 형태로 M×N 크기의 2차원 bool 배열을 만든다
   • 직사각형이 주어지면 해당 구역을 true(막힘)로 표시한다
2. DFS 탐색
   • 아직 방문하지 않았고(!visited), 색칠되지 않은(!graph) 좌표에서 DFS를 시작
   • DFS를 통해 상하좌우로 인접한 빈 칸을 모두 탐색하며 영역의 넓이를 계산
3. 결과 저장
   • 탐색이 끝날 때마다 영역 개수를 +1 하고, 해당 영역 넓이를 벡터에 저장한다
   • 마지막에 벡터를 오름차순으로 정렬 후 출력

작성코드

#include <bits/stdc++.h>
using namespace std;

int fourway_x[4] = {0,0,1,-1};
int fourway_y[4] = {1,-1,0,0};

int DFS (vector<vector<bool>> & graph,vector<vector<bool>> & visited,int x, int y);
int M,N,K;

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> M >> N >> K;
    vector<vector<bool>> graph(N,vector<bool>(M,false));
    vector<vector<bool>> visited(N,vector<bool>(M,false));
    
    for(int i = 0; i < K; i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int x = x1; x < x2; x++){
            for(int y = y1; y < y2; y++){
                graph[x][y] = true;
            }
        }
    }

    int count_parts = 0;
    vector<int> count_v;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(!visited[i][j] && !graph[i][j]){
                int count = DFS(graph,visited, i, j);
                count_parts += 1;
                count_v.push_back(count);
            }
        }
    }

    sort(count_v.begin(),count_v.end());
    cout << count_parts << '\n';
    for (int i : count_v){
        cout << i << ' ';
    }

    return 0;

}

int DFS (vector<vector<bool>> & graph,vector<vector<bool>> & visited,int x, int y){
    visited[x][y] = true;
    int count = 1;

    int next_x,next_y;
    for(int i = 0; i < 4; i++){
        next_x = x + fourway_x[i];
        next_y = y + fourway_y[i];

        if(next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y] && !graph[next_x][next_y] ){
            count += DFS(graph,visited,next_x,next_y);
        }
    }

    return count;
}