[백준][JAVA] 1012 : 유기농 배추

import java.io.IOException;
import java.util.Scanner;
public class Main{
    static int[][] adjacent;
    static boolean[][] checked;
    static int n,m,k,T,temp;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        T = s.nextInt();	//테스트케이스 개수
        
        for(int j=0; j<T; j++){
            m = s.nextInt();	// col
            n = s.nextInt();	// row
            k = s.nextInt();	// 배추가 심어져있는 위치의 개수
            
            adjacent = new int[n][m];	// m : col, n : row
            checked = new boolean[n][m]; 
            
            temp=0; //새로운 test case가 입력될 때마다 초기화
            
            for(int i = 0; i <k; i++) { //배추 위치 입력 받기
                int x = s.nextInt();	// col
                int y = s.nextInt();	// row
                adjacent[y][x] = 1; // x : col, y : row
            }
            
            for(int t = 0; t < n; t++){
                for(int l = 0 ; l < m; l++){
                    if(checkLocation(t, l) == true) {
                        temp++;
                        dfs(t, l);
                    }
                }
                
            }
            sb.append(temp + "\n");
        }
        System.out.println(sb);
    }
    
    public static boolean checkLocation(int row, int col){ //true를 반환할 시에만 dfs함수 호출
        if(row < 0 || row >= n || col < 0 || col >= m) //좌표값이 잘못된 경우
        	return false;
        if(checked[row][col] == true || adjacent[row][col] == 0) //이미 지나갔거나 배추가 없는 경우
        	return false;
        return true;
    }
    
    public static void dfs(int x, int y) { //상하좌우에 배추가 있는지 확인
        checked[x][y]=true;
        if(checkLocation(x - 1, y)) dfs(x - 1, y);
        if(checkLocation(x, y + 1)) dfs(x, y + 1);
        if(checkLocation(x + 1, y)) dfs(x + 1, y);
        if(checkLocation(x, y - 1)) dfs(x, y - 1);
    }
}