백준 1012번 - 유기농 배추

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

문제가 조금 길고 처음에는 살짝 어려워 보이는 문제인데
쉽게 생각하면 배추가 있는 위치를 모두 연결한 경우를 하나의 구역이라고 생각하고 이 구역이 몇개있는지 구하는 문제이다.


DFS를 통해 배추가 놓인 지역을 방문하면 왼쪽과 오른쪽, 위쪽과 아래쪽을 모두 탐색해서 탐색한 지역은 visited한 방식으로 해결하면 된다.


그리고 문제를 풀 때, N과 M을 반대로 계산할 수 있으니 이런 부분만 주의하면 된다.


BFS로 문제를 풀 경우, 함수를 호출하는 것이 아니라 큐에 해당 x,y좌표를 집어넣은 다음에 4가지 방향으로 모두 검사해서 큐에 담으면 된다. 

#include <iostream>
#include <string.h>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int M,N,K;
int arr[50][50]={0};
int visited[50][50]={0};
 
void dfs(int y,int x){
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=M)
            continue;
        
        if(arr[ny][nx] && !visited[ny][nx]){
            visited[ny][nx]++;
            dfs(ny,nx);
        }
    }
}
int main(){
    int T,x,y;
    cin>>T;
    
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d %d %d",&M,&N,&K);
        
        memset(arr,0,sizeof(arr));
        memset(visited,0,sizeof(visited));
        
        int ans=0; //지렁이 개수
        
        for(int i=0;i<K;i++){
            scanf("%d %d",&x,&y);
            arr[y][x]=1;
        }
        
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(arr[i][j] && !visited[i][j]){
                    
                    ans++;
                    visited[i][j]++;
                    dfs(i,j);
                    
                }
        
        cout<<ans<<endl;
    }
    return 0;
}