[백준] 1023번 유기농 배추 (C)

문제 주소

백준 1012번: 유기농 배추

알고리즘

DFS, Flood Fill

힌트

Flood Fill 알고리즘을 사용하여 구역의 개수를 구한다.

 

풀이

배추들의 위치를 입력받기 전에 in배열과 check배열을 초기화 해주어야 한다. check가 되어 있지 않으면서 배추가 있는 곳을 탐색하여 주변 배추들이 있는 곳을 check한다.

 

#include<iostream>
using namespace std;

int n,m;
int in[50][50];
int check[50][50];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

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>=m||na<0||nb<0)
            continue;

        fill(na,nb);
    }
}

int main(){
    int x;
    cin>>x;
    for(int q=0;q<x;q++){
        int c,ans=0;
        cin>>m>>n>>c;

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

        }

        for(int i=0;i<c;i++){
            int a,b;
            cin>>a>>b;
            in[b][a]=1;
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(in[i][j]&&!check[i][j]){
                    fill(i,j);
                    ans++;
                }
            }
        }
        cout<<ans<<"\n";

    }
}

정확한 풀이