[JAVA] 백준 2638 - 치즈

https://www.acmicpc.net/problem/2638

빈공간과 2변 이상 인접한 치즈를 1시간마다 녹여가며 모두 빈 공간으로 만드는 데 걸리는 시간을 출력하는 문제이다.

첫번째로 고려한 항목은 빈공간 판단으로 빈 공간에 대해 dfs를 돌렸을 때 가장자리에 닿는지 아닌지로 고립 여부를 판단했다.

두번째는 이를 기반으로 녹여야하는 치즈를 정하는 것이었다.

가장자리에 닿지 않는(치즈로 둘러쌓인) 빈 공간을 2로 치환하고 

녹여야하는 치즈를 3으로 치환한 뒤

카운트를 하나 올린 후 2와 3을 0으로 치환해 모든 칸이 0이 될때까지 반복했다.

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

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int[] temp = Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] map = new int[temp[0]][temp[1]];
        for (int i = 0; i < map.length; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        int count = 0;
        while(!zeroCheck(map)){
            boolean[][] visited = new boolean[map.length][map[0].length];
            //1. 빈공간 판단
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if (map[i][j] == 0 && !visited[i][j]) {
                        boolean check = dfs(map, i, j, visited, false);
                    }
                }
            }
            //2. 녹는 치즈 판단
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if(map[i][j]==1){
                        if(meltCheck(map,i,j)){
                            map[i][j] = 3;
                        }
                    }
                }
            }
            count++;
            //3. 녹은 치즈 변환
            convert(map);
        }
        System.out.println(count);
    }

    static boolean dfs(int[][] map, int i, int j, boolean[][] visited, boolean bef) {
        boolean isBoundary = i == 0 || j == 0 || bef;
        for (int k = 0; k < 4; k++) {
            boolean isZero = check(map, i + dx[k], j + dy[k], visited);
            if (isZero) {
                visited[i + dx[k]][j + dy[k]] = true;
                isBoundary = isBoundary | dfs(map, i + dx[k], j + dy[k], visited, isBoundary);
            }
        }
        if (!isBoundary) map[i][j] = 2;
        return isBoundary;
    }

    static boolean check(int[][] map, int i, int j, boolean[][] visited) {
        if (!boundaryCheck(map, i, j)) return false;
        return !visited[i][j];
    }

    static boolean meltCheck(int[][] map, int i, int j) {
        int count = 0;
        for (int k = 0; k < 4; k++) {
            if(boundaryCheck(map,i+dx[k],j+dy[k])) count++;
        }
        return count >= 2;
    }

    static boolean boundaryCheck(int[][] map, int i, int j) {
        if (i < 0 || i >= map.length || j < 0 || j >= map[0].length) return false;
        return map[i][j] == 0;
    }
    static boolean zeroCheck(int[][] map){
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if(map[i][j]!=0){
                    return false;
                }
            }
        }
        return true;
    }

    static void convert(int[][] map){
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if(map[i][j]>1){
                    map[i][j] = 0;
                }
            }
        }
    }
}