[DFS] 백준 1012 유기농배추 JAVA

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

public class D_1_1012 {
    // [DFS] 1012 유기농배추
    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());
        String[] temp;
        for (int i = 0 ; i < T ; i++) {
            temp = br.readLine().split(" ");
            weight = Integer.parseInt(temp[0]);
            height = Integer.parseInt(temp[1]);
            ground = new int[weight][height]; // 각 요소 0으로 초기화
            check = new boolean[weight][height]; // 각 요소 false로 초기화

            int cabbages = Integer.parseInt(temp[2]);
            for (int j = 0 ; j < cabbages ; j++) {
                temp = br.readLine().split(" ");
                int x = Integer.parseInt(temp[0]);
                int y = Integer.parseInt(temp[1]);
                ground[x][y] = 1; // 배추 심기
            }
            int count = 0; // 테스트 케이스마다 출력할 벌레 개수
            for (int m = 0 ; m < weight ; m++) {
                for (int n = 0 ; n < height ; n++) {
                    if (ground[m][n] == 1 && !check[m][n]) {
                        // 배추가 심겨져 있고, 아직 순회하지 않았으면(check = false)
                        dfs(m, n);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    static void dfs(int x, int y) {
        check[x][y] = true;

        int[] moveX = {0, 0, -1, +1};
        int[] moveY = {-1, +1 ,0 , 0};

        // 상하좌우 돌면서 확인
        for (int i = 0 ; i < 4 ; i++) {
            int m = x + moveX[i];
            int n = y + moveY[i];

            // 범위 초과인지 확인
            if (m < 0 || n < 0 || m > weight-1 || n > height-1) {
                continue;
            }

            if (ground[m][n] == 1 && !check[m][n]) {
                dfs(m, n);
            }

        }
    }
}

 

시간 복잡도 : O(W * H)     W: 배추밭의 가로 크기, H: 세로 크기