백준 1012번 문제 - 유기농 배추

---

문제 링크 : https://www.acmicpc.net/problem/1012

유기농 배추 문제는 DFS 또는 BFS를 통해 해결할 수 있다.

DFS란 깊이 우선 탐색(Depth-First Search), BFS란 너비 우선 탐색(Breadth-First Search)으로서 모든 정점을 한 번씩만 방문하여 모든 노드를 탐색하는 그래프 탐색 알고리즘이다.

명칭에서도 알 수 있듯이, DFS는 깊이 우선 탐색으로 더 이상 이동할 수 있는 노드가 없을 때까지 연결된 노드를 지속적으로 방문한 후 이전 노드로 돌아가 연결된 다른 노드를 방문하는 backtracking 방식을 사용하며 BFS는 너비 우선 탐색으로 노드에 가까운 노드들을 모두 방문한 후에 해당 노드들에 연결된 노드를 방문하는 방식으로 구현되어있다.

DFS의 경우 깊이를 우선시 하기 위해 LIFO인 stack을 사용하거나 재귀함수를 사용하여 탐색할 수 있으며, BFS의 경우 너비를 우선시 하기 위해 FIFO인 queue를 사용한다.

유기농 배추 문제는 배추가 심어져 있는 땅의 위치 X와 Y를 입력으로 받는다.
입력받은 배추들을 확인할 예정에 두고 인접한 위치에 배추가 존재하지 않을 때까지 방문하지 않은 인접 배추들을 확인하도록 하여 그룹을 체크할 수 있다.

#include<iostream>
#include<vector>
using namespace std;
#define MAXSIZE 51
int T,M,N,K;
int arr[MAXSIZE][MAXSIZE]={0};
bool bvisited[MAXSIZE][MAXSIZE]={false};
vector<pair<int,int>> vec;
int result=0;

void grouping(int x, int y){
    bvisited[x][y]=true;
    if(x>0&&arr[x-1][y]&&!bvisited[x-1][y]){
        grouping(x-1,y);
    }
    if(x+1<M&&arr[x+1][y]&&!bvisited[x+1][y]){
        grouping(x+1,y);
    }
    if(y>0&&arr[x][y-1]&&!bvisited[x][y-1]){
        grouping(x,y-1);
    }  
    if(y+1<N&&arr[x][y+1]&&!bvisited[x][y+1]){
        grouping(x,y+1);
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&M,&N,&K);
        vec.clear();
        result=0;
        for(int i=0;i<N;i++){//y
            for(int j=0;j<M;j++){//x
                bvisited[i][j] = false;
                arr[i][j]=0;
            }
        }
        while(K--){
            int i,j;
            scanf("%d %d",&i,&j);
            arr[i][j] =1;
            vec.push_back(make_pair(i,j));
        }
        for(int i=0;i<vec.size();i++){
            int x = vec[i].first;
            int y = vec[i].second;
            if(!bvisited[x][y]){
                grouping(x,y);
                result++;
            }
        }
        printf("%d\n",result);

    }
    return 0;
}