백준 1012 - 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

문제

---

유기농 배추밭에 필요한 흰 지렁이의 개수를 구하는 문제로 인접하여 생기는 배추 영역의 개수가 전체 필요한 지렁이의 개수이다.

 

문제 풀이 

---

전형적인 BFS, DFS 문제이다. 영역의 개수를 구하는 것이 핵심 포인트이며 정답이 된다.

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int M,N,K,testcase,ans=0;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int map[50][50]={0,};

bool inside(int x,int y){	//메트릭스에 좌표가 포함되는지 확인하는 함수
    return ((x>=0&&x<M)&&(y>=0&&y<N));
}

void bfs(int x,int y){	//BFS 함수
    map[x][y] = 0;
    queue<pair<int,int> >q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(inside(nx,ny)&&map[nx][ny]==1){
                q.push(make_pair(nx,ny));map[nx][ny]=0;
            }
        }
    }
}

int main(void){
    std::ios::sync_with_stdio(false); cin.tie(0);
    scanf("%d", &testcase);
    while(testcase--){	//테스트케이스 개수만큼 받기 
        scanf("%d %d %d", &M, &N, &K);
        for(int i=0;i<K;i++){
            int x,y;
            scanf("%d %d", &x, &y);
            map[x][y]=1;
        }
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==1){
                    bfs(i,j);ans++;
                }
            }
        }
        printf("%d\n",ans); //필요한 지렁이의 개수 
        for(int i=0;i<M;i++){	//map 초기화 장치
            for(int j=0;j<N;j++){
                map[i][j]=0;
            }
        }
        ans=0;   //지렁이 개수 초기화
    }
}