[알고리즘] 백준 2583

백준 2583번 영역 구하기

해결 과정 요약

0으로 초기화된 2차원 배열을 만들고
입력을 받으면서 작은 직사각형들의 내부에 속하는 점들을 1로 바꾸어준다.
DFS를 이용해 점들을 탐색하면서 분리된 영역의 개수 및 각각의 넓이를 구해준다.

int ret // 분리된 영역의 수
int num // 분리된 영역의 넓이. for문을 돌면서 1로 초기화시키고 
		// DFS가 재귀호출될 때마다 +1 해준다.

풀이

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

int M,N,K,ly,lx,ry,rx,ret,num;
vector<int> area;
int a[104][104];
int v[104][104];
int dy[4] = {-1, 0 ,1, 0};
int dx[4] = {0, 1, 0 ,-1};

void dfs(int y, int x){
    v[y][x] = 1;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
        if(a[ny][nx] || v[ny][nx]) continue;
        num++;
        dfs(ny, nx);
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> M >> N >> K;
    for(int i=0; i<K; i++){
        cin >> lx >> ly >> rx >> ry;
        for(int j=ly; j<ry; j++){
            for(int k=lx; k<rx; k++){
                a[j][k] = 1;
            }
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(a[i][j] || v[i][j]) continue;
            ret++; num = 1;
            dfs(i, j);
            area.push_back(num);
        }
    }
    sort(area.begin(), area.end());
    cout << ret << "\n";
    for(int e : area) cout << e << " ";
    
    return 0;
}

코멘트

최근 그래프 문제를 집중적으로 풀고있다.
아주 기본적인 구현과 DFS를 이용하면 간단하게 풀 수 있는 문제였다.