백준 2636번
https://www.acmicpc.net/problem/2636

문제

---

생각하기

---

• 방법만 잘 생각하면 쉽게 풀 수 있다.
  • 치즈를 탐색하는 것이 아닌 공기를 위주로 탐색한다.

동작

 for (; ; ) {
            isVisited = new boolean[N][M];
            area = 0;
            DFS(0, 0);
            boolean onlyZero = true;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == 1) {
                        onlyZero = false;
                        break;
                    }
                }
                if (!onlyZero) {
                    break;
                }
            }

            if (onlyZero) {
                System.out.println(time); // 치즈가 모두 녹아서 없어지는데 걸리는 시간
                System.out.println(area); // 치즈가 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수
                return;
            }

            time++;
        }

2차원 배열의 가장 바깥쪽 라인은 항상 0을 유지하므로, 0,0부터 DFS탐색을 시작하도록 했다.

치즈가 모두 녹아 없어지는데 걸리는 시간, 모두 녹기 직전에 남아있는 치즈 조각을 구하는 문제이므로, 치즈가 언제 모두 없어질지 모르는 상태이기 때문에 for(;;)로 무한 반복을 해주었다.

onlyZero 라는 boolean형 변수를 주어 2차원 배열이 모두 0으로 이루어져있는지 검사한다. 만약 1이 하나라도 있으면 아직 치즈가 남아 있다는 것이므로, 계속해서 DFS 탐색을 통해 치즈를 줄여나간다.

            if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && arr[nowX][nowY] == 1) {
                area++;
                arr[nowX][nowY]--;
                isVisited[nowX][nowY] = true;
            }

DFS탐색에서는 이 부분이 핵심이다. 0인 공기를 위주로 탐색한다. 만약 같은 공기인 0을 만났을 경우 계속 DFS 함수를 실행하고, 1을 만났을 경우에는 해당 1값을 빼줘서 0으로 만들고, DFS함수를 실행하지 않고 종료를 하도록 했다.

코드

---

Java

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

public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[][] isVisited;
    static int[] dirX = {0, 0, -1, 1};
    static int[] dirY = {1, -1, 0, 0};

    static int area;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];

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

        int time = 1;
        for (; ; ) {
            isVisited = new boolean[N][M];
            area = 0;
            DFS(0, 0);
            boolean onlyZero = true;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == 1) {
                        onlyZero = false;
                        break;
                    }
                }
                if (!onlyZero) {
                    break;
                }
            }

            if (onlyZero) {
                System.out.println(time); // 치즈가 모두 녹아서 없어지는데 걸리는 시간
                System.out.println(area); // 치즈가 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수
                return;
            }

            time++;
        }
        
    } // End of main

    private static void DFS(int x, int y) {
        isVisited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nowX = dirX[i] + x;
            int nowY = dirY[i] + y;

            if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && arr[nowX][nowY] == 1) {
                area++;
                arr[nowX][nowY]--;
                isVisited[nowX][nowY] = true;
            }

            if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && arr[nowX][nowY] == 0) {
                isVisited[nowX][nowY] = true;
                DFS(nowX, nowY);
            }
        }
    } // End of DFS

    private static boolean rangeCheck(int nowX, int nowY) {
        return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M;
    } // End of rangeCheck
} // End of Main class