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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 백준 1012번: 유기농 배추
 */
public class Main {
    private static boolean[][] field;
    private static Queue<int[]> queue;
    
    // 델타 배열 생성 (위에서부터 시계 방향)
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};
    
    private static int m, n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            int minWormCnt = 0;
            
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            
            field = new boolean[n][m];
            queue = new LinkedList<>();
            
            // 배추 초기화
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                int c = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                
                field[r][c] = true;
            }
            
            // 처음부터 순회하면서 배추가 심어져 있는 경우 BFS 수행 & 배추흰지렁이 마릿수 증가
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    if (field[r][c]) {
                        bfs(r, c);
                        minWormCnt++;
                    }
                }
            }
            
            sb.append(minWormCnt + "\n");
        }
        
        System.out.print(sb.toString());
        br.close();
    }
    
    public static void bfs(int initRow, int initCol) {
        queue.offer(new int[] {initRow, initCol});
        
        while (!queue.isEmpty()) {
            // 큐에서 원소 추출
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];
            
            // 범위 밖으로 나가면 패스
            if (r < 0 || r >= n || c < 0 || c >= m) continue;
            
            // 이미 방문하거나 배추가 심어져 있지 않은 땅이라면 원소라면 패스
            if (!field[r][c]) continue;
            field[r][c] = false;
            
            // 4방향 탐색
            for (int dir = 0; dir < 4; dir++) {
                queue.offer(new int[] {r + dr[dir], c + dc[dir]});
            }
        }
    }
}