[백준] 1012번(java 자바)

import java.util.*;

public class Main
{   
    static final int MAX_N = 51;
    static int T, M, N, K;
    static boolean[][] visited;
    static int[][] matrix;
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static class Point{
        Point(int r, int c){
            row = r; col = c;
        }
        int row, col;
    }
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        // 두 번 반복 
        for(int a = 0; a < T; a++){
        
            M = sc.nextInt();
            N = sc.nextInt();
            K = sc.nextInt();
            
            // 초기화 
            visited = new boolean[MAX_N][MAX_N];
            matrix = new int[MAX_N][MAX_N];
    
            for(int i=0; i<K; i++){
                int v = sc.nextInt();
                int u = sc.nextInt();
                matrix[u][v] = 1;
            }
            
            int cnt = 0;

            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(matrix[i][j] == 1 && !visited[i][j]){
                        bfs(i, j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        
        }
	}
	static void bfs(int u, int v){
        Queue<Point> myqueue = new LinkedList<>();
        myqueue.add(new Point(u, v));
        visited[u][v] = true;

        while(!myqueue.isEmpty()){
            Point curr = myqueue.remove();
            
            
            for(int i = 0; i < 4; i++){
                int nr = curr.row + D[i][0];
                int nc = curr.col + D[i][1];
                if(nr < 0 || nr > N - 1 || nc < 0 || nc > M - 1) continue;
                if(visited[nr][nc]) continue;
                if(matrix[nr][nc] == 0) continue;
                myqueue.add(new Point(nr, nc));
                visited[nr][nc] = true;
            }
        }
        
	    }
	}