[코드업] 4060 : 전광판 전구 조작 (C)

문제 번호

코드업 4060 : 전광판 전구 조작

알고리즘

DFS, Flood Fill

힌트

0일때와 1일때 모두 Flood Fill 알고리즘을 사용한다.

 

풀이

문제 이해를 잘 했다면 별 탈 없이 풀리는 문제이다. 플러드 필 알고리즘을 사용하여 0인 영역과 1인 영역의 개수를 세어주면 된다.

#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,m;

int 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]!=in[a][b]||check[na][nb]||na>=n||nb>=m||na<0||nb<0)
            continue;
        fill(na,nb);
    }
}

int main(){

    cin>>n>>m;

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

    int on=0,off=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){

            if(!check[i][j]){
                fill(i,j);
                if(in[i][j]==1)
                    off++;
                else
                    on++;
            }
        }
    }

    cout<<on<<" "<<off;

}