백준 1012번(Java)

import java.io.*;
import java.util.*;

public class Main {
	
    static int[][] ground;      //2차원 배열 배추밭
    static boolean[][] check;   //2차원 배열 배추가 있는 곳 체크
    static int weight;          //배추밭의 가로
    static int height;          //배추밭의 세로

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            weight = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            ground = new int[weight][height];
            check = new boolean[weight][height];

            int K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                ground[x][y] = 1;   //배추 좌표 입력
            }

            int count=0;
            
            //bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악
            //가로 세로 좌표 하나씩 입력
            for (int j = 0; j < weight; j++) {
                for (int k = 0; k < height; k++) {
                    
                    //좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인
                     if(ground[j][k] == 1 && !check[j][k]){
                         //배추가 있고 체크안된 좌표에서부터 bfs로 연결된 곳을 파악
                         bfs(j, k);
                         
                         //지렁이의 개수는 인접한 곳마다 1개씩
                         //인접한 곳을 모두 파악했으면 지렁이를 한마리 놓기
                         count++;
                     }
                }
            }

            System.out.println(count);
        }

    }

    private static void bfs(int startX, int startY) {
        //bfs에서 queue의 역할은 다음 탐색할 좌표를 미리 저장해 놓는 것
        //bfs 1번 실행될때마다 인접한 곳을 모두 탐색하고 종료되니 bfs안에 queue를 선언
    	Queue<int[]> queue = new LinkedList<>();
        
        //x, y좌표 저장
    	queue.offer(new int[] {startX, startY});
        
        //시작좌표엔 배추가 있으니 미리 true로 처리
    	check[startX][startY] = true;
        
        //배추가 상하좌우에 인접하면 이동 가능
        //현재좌표에서 상하좌우 움직이는 좌표를 지정
    	int[] X = {0, 0, -1, +1};
    	int[] Y = {-1, +1, 0, 0};

        //queue가 비어있으면 더이상 인접한 배추가 없다는 뜻
        while(!queue.isEmpty()){
            //저장된 queue를 꺼낸다
        	int[] poll = queue.poll();
            
            //상하좌우 4가지 방법이니 for문 4번 반복
            for (int i = 0; i < 4; i++) {
            	//상하좌우 좌표 조정
                int x = poll[0] + X[i];
                int y = poll[1] + Y[i];

                //좌표가 배추밭을 벗어나게되면 다음 좌표를 체크
                if(x < 0 || x >= weight || y < 0 || y >= height){
                    continue;
                }

                //상하좌우 움직인 좌표에 배추가 있고, 체크하지 않은 좌표이면
                if(ground[x][y] == 1 & !check[x][y]){
                	//좌표를 저장
                    queue.offer(new int[] {x, y});
                    
                    //체크
                    check[x][y] = true;
                }

            }
        }

    }
}