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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Dot{
	int x;
	int y;
	public Dot(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int map[][]; // 2차원 미로 배열
	static boolean visit[][]; // 2차원 방문여부 배열
	static int n, m, ca;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void bfs(int x, int y) { //BFS메소드
		
		Queue<Dot> q = new LinkedList<>();
		q.offer(new Dot(x,y)); 
		
		while(!q.isEmpty()) {
			
			Dot dot = q.poll();

			//방문표시
			visit[dot.x][dot.y] = true;
			
			//상하좌우 4방향 노드 범위 벗어나는지 탐색
			for(int i = 0; i < 4; i++) {
				int qx = dot.x + dx[i];
				int qy = dot.y + dy[i];
				
				if(qx >= 0 && qx < m && qy >= 0 && qy < n)
					//배추가 있고 방문하지 않았을때 
					if(map[qx][qy] == 1 && !visit[qx][qy]) {
						q.add(new Dot(qx,qy));
						visit[qx][qy] = true;
					}
			}
		}
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {			
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			ca = Integer.parseInt(st.nextToken());
			
			map = new int[m][n];
			visit = new boolean[m][n];
			
			for(int i = 0; i < ca; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				map[x][y] = 1;
			}
			int part = 0;//구역 수
			for(int i = 0; i < m; i++) 
				for(int j = 0; j < n; j++) 
					if(map[i][j] == 1 && !visit[i][j]) {
						bfs(i,j);
						part++;
					}
			System.out.println(part);
		}
	}
}