유기농배추(백준 1012) - DFS

💡주의

1. graph[행=세로N][열=가로M] 구분
   행이동 : {-1, 1, 0, 0};
   열이동 : {0, 0, -1, 1};

2. 범위체크 (0 ~ N과 M 이내의 범위)

정답

package A0study;

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

public class p1012_유기농배추 {
    // 전역 변수
    static int[][] graph;
    static boolean[][] visited;
    static int M, N;    // 행, 열

    // 방향 벡터
    static final int[] dx = {-1, 1, 0, 0}; // 행 이동
    static final int[] dy = {0, 0, -1, 1}; // 열 이동

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

        for (int test = 0; test < T; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            graph = new int[N][M];
            visited = new boolean[N][M];

            // graph에 배추 심기
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st.nextToken()); // 가로=열
                int x = Integer.parseInt(st.nextToken()); // 세로=행
                graph[x][y] = 1;
            }

            // 배추흰지렁이 수 구하기
            int count = 0;
            for (int i = 0; i < N; i++) {        // 세로=행
                for (int j = 0; j < M; j++) {    // 가로=열
                    if (graph[i][j] == 1 && !visited[i][j]) {   // 현재 위치가 방문한적 없고 + 배추면
                        dfs(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

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

        // 상하좌우 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 체크 (0 ~ N과 M 이내의 범위)
            if(nx >=0 && nx < N && ny >= 0 && ny < M) {
                if (graph[nx][ny] == 1 && !visited[nx][ny]) {   // 현재 위치가 방문한적 없고 + 배추면
                    dfs(nx, ny);
                }
            }
        }
    }
}