#백준_1012 유기농 배추 - Java 자바

# 유형 : 탐색(DFS,BFS)

# BFS를 통해 문제를 풀었다. 큐에 넣기전에 방문 체크를 해주고 넣어야 하는데 생각없이 큐에서 poll해서 방문 체크를 해줘서 계속 시간초과가 났다. 당연한 것인데 이것때문에 시간을 버렸다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1012 {
    static int M,N,K;
    static int arr[][];
    static boolean visit[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            
            arr = new int[N][M];
            visit = new boolean[N][M];
            int count = 0;
            for(int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
 
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr[y][x] = 1;
            }
            
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(arr[i][j] == 1 && !visit[i][j]) {
                        bfs(i,j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
    public static void bfs(int i, int j) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(j,i));
        visit[i][j] = true;
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            int y = p.y;
            int x = p.x;
        
            for(int d=0; d<4; d++) {
                int newY = y + moveY[d];
                int newX = x + moveX[d];
            
                if(0<=newY && newY<N && 0<=newX && newX<M) {
                    if(arr[newY][newX] == 1 && !visit[newY][newX]) {
                        visit[newY][newX] = true;
                        queue.add(new Point(newX,newY));
                    }
                }
            }
        }
    }
}