[백준] 2468번 안전영역 (C)

출처

한국정보올림피아드 KOI 2010 초등부 2번

문제 번호

백준 : 4697 안전 영역
코드업 : 2468번 안전 영역

알고리즘

DFS, Flood Fill

 

 

풀이

수면의 높이를 0부터 100까지 올려가면서 구역의 개수를 세어준다.(cnt) 각 수면의 높이마다 ans를 최대 값으로 갱신해준다. 매 높이 마다 구역을 새로 세어야 하기 때문에 check배열을 매번 초기화 해주어야 한다.

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

void fill(int a, int b){
    check[a][b]=1;
    for(int i=0;i<4;i++){
        int na=a+dir[i][0], nb=b+dir[i][1];

        if(!in[na][nb]||check[na][nb]||na>=n||nb>=n||nb<0||na<0)
            continue;

        fill(na,nb);
    }    
}


int main(){
    cin>>n;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>in[i][j];
        }
    }

    int ans=0;

    for(int h=0; h<=100; h++){

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(in[i][j]<=h)
                    in[i][j]=0;
                check[i][j]=0;    
            }
        }

        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(check[i][j]||!in[i][j])
                    continue;

                fill(i,j);
                cnt++;
            }
        }

        if(cnt==0)
            break;

        ans=max(cnt,ans);
    }    

    cout<<ans;
}