[백준] 2583번 영역 구하기 (C)

출처 : 한국정보올림피아드 지역본선 2006 고등부 2번

알고리즘 : Flood Fill

풀이

전형적인 Flood Fill 문제이다. 다만 조심해야 할 것은 입력값이 좌표로 주어진다는 것이다. 좌 상단에서 우하단으로 내려가는 좌표계가 아닌 좌하단에서 우 상단으로 올라가는 좌표계지만 크게 신경쓸 필요는 없다. (뒤집어도 결과는 똑같다.)
좌표값으로 입력되기 때문에 첫 번째 좌표 (a1, b1)은 그대로 인덱스 값이고, 두번째 좌표 (a2,b2)는 인덱스보다 1씩 큰 값이다. 입력값에 해당하는 만큼의 영역을 check배열에 채워준다. 그 뒤 Flood Fill 알고리즘을 사용하여 구간별 크기를 ans 벡터에 넣어준다. 그 뒤 오름차순으로 정렬하고 벡터의 사이즈와 요소 값들을 출력해준다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int check[100][100];
vector<int> ans;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m,k;

int fill(int a, int b){

    check[a][b]=1;
    int cnt=1;
    for(int i=0;i<4;i++){
        int na=a+dir[i][0], nb=b+dir[i][1];
        if(check[na][nb]||na<0||nb<0||na>=n||nb>=m)    
            continue;
        cnt+=fill(na,nb);
    }

    return cnt;
}

int main(){

    cin>>n>>m>>k;    

    for(int i=0;i<k;i++){
        int a1,b1,a2,b2;
        cin>>a1>>b1>>a2>>b2;

        for(int j=a1;j<a2;j++){
            for(int l=b1;l<b2;l++){
                check[l][j]=1;
            }
        }

    }



    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!check[i][j])
                ans.push_back(fill(i,j));
        }
    }

    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
}

---

백준 2584번 코드업 4572 영역 구하기