[백준] 영역 구하기

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

2583번: 영역 구하기

DFS를 이용한 floodfill 기본문제입니다.

 

우선 문제부터 간단하게 요약해보면, 

모눈종이에 검정색 직사각형들이 그려져 흰 구역들이 분리가 되게 됩니다. 이 때, 분리되어 나누어지는 영역의 개수와, 각 영역의 넓이를 오름차순으로 정렬하여 출력하는 문제입니다. 

 

<Solution>

 모눈종이에 검정색 영역들을 먼저 모두 채웁니다. 

 

다음으로 흰 영역에서 floodfill하여 영역의 크기를 계산해줍니다. 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX (100)
int M, N, K;//세로크기, 가로크기, 직사각형 개수
int sx[MAX+10];
int sy[MAX+10];
int ex[MAX+10];
int ey[MAX+10];
 
int sol[MAX * MAX];//각 영역 넓이 저장용
 
int grid[MAX][MAX];
 
int d_row[] = {0, 0, 1, -1};
int d_col[] = {-1, 1, 0, 0};
 
void InputData(){
    cin >> M >> N >> K;
    for (int i=0; i<K; i++){
        cin >> sx[i] >> sy[i] >> ex[i] >> ey[i];// c r c r 순서
    }
}
void OutputData(int ans){
    cout << ans << endl;
    for (int i=0; i<ans; i++){
        cout << sol[i] << " ";
    }
    cout << endl;
}
 
void ff(int r, int c, int& k){
    if(grid[r][c] != 0) return;
    grid[r][c] = 1;
    k++;
 
    for(int i = 0; i<4; i++){
        int new_r = r+d_row[i];
        int new_c = c+d_col[i];
 
        if(!(0<=new_r && new_r < M && 0<=new_c && new_c < N)) continue;
 
        ff(new_r, new_c, k);
    }
}
 
int solution(){
    int cnt = 0;
    // fill grid
    for(int i = 0; i<K; i++){
        for(int c = sx[i]; c<ex[i]; c++){
            for(int r = sy[i]; r<ey[i]; r++){
                grid[r][c] = 1;
            }
        }
    }
    
    // flood fill
 
    for(int r = 0; r<M; r++){
        for(int c= 0; c<N; c++){
            // flood fill
            if(grid[r][c] == 0){
                 
                ff(r,c, sol[cnt]);
                cnt ++; 
            }
        }
    }
 
 
    return cnt;
 
}
 
 
int main(void){
    int ans = -1;
    InputData();

    ans = solution();
 
    sort(sol, sol+ans);
 
    OutputData(ans);
    return 0;
}