문제 유기농 배추

문제링크
실버 2
그래프 탐색

어떤 좌표 기준으로 상하좌우로 인접해있으면 해충 X
배추밭이 몇덩어리인지 구하시오

입력

테스트케이스 갯수 T
가로길이 M, 세로길이 N 배추개수 K
배추의 위치 X,Y (K줄)

출력

최소의 배추흰지렁이 마리 수

풀이

1. 테스트 케이스 만큼 입력 받는 반복문
2. 격자형으로 상하좌우 탐색하는 코드 =>find 함수
3. 더이상 배추가 없으면 돌아와서 cnt +1 추가해주기
4. 위를 반복후 cnt 출력해주기

코드

import java.util.*;

public class 백준1012 {
	static int T,M,N,cnt=0;
	static Scanner scan =new Scanner(System.in);
	static int[] dx= {1,0,0,-1};
	static int[] dy= {0,-1,1,0};
	static boolean[][] visited;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		T=scan.nextInt();
		for(int i=0;i<T;i++) {
			cnt=0;
			M=scan.nextInt();
			N=scan.nextInt();
			int K=scan.nextInt();
			boolean[][] arr=new boolean[M+1][N+1];
			visited=new boolean[M+1][N+1];
			for(int j=0;j<K;j++) {
				int a=scan.nextInt();
				int b=scan.nextInt();
				arr[a][b]=true;
			}
			for(int m=0;m<M;m++) {
				for(int n=0;n<N;n++) {
					if(arr[m][n]&&!visited[m][n]) {
						find(arr,m,n);
						cnt++;
					}
				}
			}
			sb.append(cnt+"\n");
		}
		System.out.print(sb);
	}
	static void find(boolean[][] arr,int m,int n) {
		if(!visited[m][n]&&arr[m][n]) {
			visited[m][n]=true;
			for(int i=0;i<4;i++) {
				int a=m+dx[i];
				int b=n+dy[i];
				if(a<=M&&a>=0&&b<=N&&b>=0) {
					if(!visited[a][b]) {
						find(arr,a,b);
					}
				}
			}
		}
	}

}