백준 1012: DFS로 유기농 배추의 연결 구역 세기

백준 1012번: 유기농 배추는 상하좌우로 연결된 배추를 한 묶음으로 세는 문제입니다. 재귀 DFS로 연결된 칸을 모두 방문했습니다.

연결된 배추를 0으로 바꿉니다

배열의 첫 칸부터 차례로 확인했습니다. 값이 1이면 그 칸을 0으로 바꾸고 상하좌우로 DFS를 이어 갑니다. 한 번의 탐색이 끝나면 연결된 배추가 모두 0이 되므로 별도의 방문 배열 없이 중복 탐색을 막을 수 있습니다.

바깥쪽 반복문에서 dfs()가 true를 반환할 때만 구역 수를 늘립니다. 이미 방문한 곳이나 배추가 없는 곳에서는 false를 반환합니다.

당시에는 바이러스가 배추를 찾아다니며 자신과 주변의 1을 0으로 바꾼다고 생각하니 이해가 쉬웠습니다. 그런데 구현 중에는 가로와 세로를 뒤섞어서 막혔습니다. 입력의 M은 가로, N은 세로이므로 배열은 arr[N][M]이고 입력 좌표 (a, b)는 arr[b][a]에 넣어야 합니다.

풀이 코드

입력한 지도를 확인하는 //임시 맵 출력 구간까지 포함한 코드입니다. 정답 외에 지도와 빈 줄을 출력하므로 제출할 때는 이 구간을 빼야 합니다.

Java

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

class Main {
    static int[][] arr;
    static int M, N, K;
    static StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            arr = new int[N][M];

            K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[b][a] = 1;
            }

            //임시 맵 출력
            bw.newLine();
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    bw.write(arr[j][k] + " ");
                }
                bw.flush();
                bw.newLine();
            }
            bw.newLine();
            // 여기까지

            int result = 0;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (dfs(j, k)) {
                        result++;
                    }
                }
            }
            sb.append(result).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    static boolean dfs(int x, int y) {
        if (-1 >= x || x >= N || -1 >= y || y >= M) {
            return false;
        }
        if (arr[x][y] == 1) {
            arr[x][y] = 0;
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }
}