[백준] 1012번

 

public class Main {

    static int T, M, N, K, X, Y, count;
    static int[][] map;
    static boolean[][] checked;
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());    // 테스트 케이스의 개수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());   // 가로 길이
            N = Integer.parseInt(st.nextToken());   // 세로 길이
            K = Integer.parseInt(st.nextToken());   // 배추가 심어져 있는 위치의 개수
            map = new int[M][N];
            checked = new boolean[M][N];
            count = 0;

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                map[x][y] = 1;
            }

            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if (map[j][k] == 1 && !checked[j][k]) {
                        bfs(j, k);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    private static void bfs(int i, int j) {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{i, j});
        checked[i][j] = true;

        while (!que.isEmpty()) {
            int[] now = que.poll();

            for (int k = 0; k < 4; k++) {
                X = now[0] + dx[k];
                Y = now[1] + dy[k];

                if (X >= 0 && Y >= 0 && X < M && Y < N) {
                    if (map[X][Y] == 1 && !checked[X][Y]) {
                        que.add(new int[]{X, Y});
                        checked[X][Y] = true;
                    }
                }
            }
        }
    }
}