[백준/2638] 치즈 (골드3) JAVA

package task.gold.cheese2638;


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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int M;
    static int[][] cheeseMap;
    static int[] dRow = new int[] {1, -1, 0, 0};
    static int[] dCol = new int[] {0, 0, 1, -1};
    static int count;
    static boolean isChanged = true;
    static int loop;
    static int[] noCheeseZone;
    static Deque<int[]> deque;
    static boolean[][] visited;



    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        noCheeseZone = new int[] {0, M-1};
        deque = new ArrayDeque<>();

        cheeseMap = new int[N][M];

        setCheeseMap();
        loop = 0;
        while (isChanged) {
            restructMap();
            loop++;
        }
        System.out.println(loop-1);
    }
    private static void restructMap() {
        isChanged = false;

        checkInside();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cheeseMap[i][j] == 1) {
                    cheackMeltingCheese(i,j);
                }
            }
        }


        // 변화 로직
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cheeseMap[i][j] == 3) {
                    isChanged = true;
                    cheeseMap[i][j] = 0;
                } else if (cheeseMap[i][j] == -1) {
                    cheeseMap[i][j] = 0;
                }
            }
        }



    }

    private static void cheackMeltingCheese(int i, int j) {
        int count = 0;
        for (int k = 0; k < 4; k++) {
            if (    i+dRow[k] >= 0
                    && i+dRow[k] < N
                    && j+dCol[k] >= 0
                    && j+dCol[k] < M
            ) {
                if (cheeseMap[i+dRow[k]][j+dCol[k]] == -1
                ) {
                    count++;
                }
            }
            if (count > 1) {
                cheeseMap[i][j] = 3;
            }
        }
    }

    private static void setCheeseMap() throws IOException {
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                cheeseMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void checkInside() {
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            if (i == 0 || i == N-1) {
                for (int j = 0; j < M; j++) {
                    if (cheeseMap[i][j] == 0) {
                        BFS(i,j);
                    }
                }
            } else {
                for (int j = 0; j < 2; j++) {
                    if (cheeseMap[i][j] == 0) {
                        BFS(i,j);
                    }
                }
            }
        }
    }

    private static void BFS(int i, int j) {
        deque.offer(new int[] {i,j});
        cheeseMap[i][j] = -1;


        while (!deque.isEmpty()) {
            int[] poll = deque.poll();
            int r = poll[0];
            int c = poll[1];

            for (int k = 0; k < 4; k++) {
                if (    r+dRow[k] >= 0
                        && r+dRow[k] < N
                        && c+dCol[k] >= 0
                        && c+dCol[k] < M
                ) {
                    if (cheeseMap[r+dRow[k]][c+dCol[k]] == 0 && !visited[r+dRow[k]][c+dCol[k]]) {
                        deque.offer(new int[] {r+dRow[k], c+dCol[k]});
                        cheeseMap[r+dRow[k]][c+dCol[k]] = -1;
                        visited[r+dRow[k]][c+dCol[k]] = true;
                    }
                }

            }
        }
    }
}

• 시간, 메모리를 크게 고려안해도 되는 문제 : N, M이 작음, 최대 100x100
• 같혀있는 0과 테두리와 연결된 0을 구분하는 로직이 우선 필요
• 두 변이 테두리와 연결된 0과 연결된 경우의 1을 3으로 바꾸기 -> BFS로 처리
• 3을 0으로 바꾸고 -1을 0으로 바꾸기
• 위 과정 3이 처리 안되는 시점까지 반복해주기

======== 전처리 ========
Arrays.toString(cheeseMap[i]) = [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Arrays.toString(cheeseMap[i]) = [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Arrays.toString(cheeseMap[i]) = [-1, 3, 3, -1, -1, -1, 3, 3, -1]
Arrays.toString(cheeseMap[i]) = [-1, 1, 0, 1, 1, 1, 0, 1, -1]
Arrays.toString(cheeseMap[i]) = [-1, 1, 0, 0, 1, 0, 0, 1, -1]
Arrays.toString(cheeseMap[i]) = [-1, 1, 0, 1, 1, 1, 0, 1, -1]
Arrays.toString(cheeseMap[i]) = [-1, 3, 3, -1, -1, -1, 3, 3, -1]
Arrays.toString(cheeseMap[i]) = [-1, -1, -1, -1, -1, -1, -1, -1, -1]
======== 변화 후 ========
Arrays.toString(cheeseMap[i]) = [0, 0, 0, 0, 0, 0, 0, 0, 0]
Arrays.toString(cheeseMap[i]) = [0, 0, 0, 0, 0, 0, 0, 0, 0]
Arrays.toString(cheeseMap[i]) = [0, 0, 0, 0, 0, 0, 0, 0, 0]
Arrays.toString(cheeseMap[i]) = [0, 1, 0, 1, 1, 1, 0, 1, 0]
Arrays.toString(cheeseMap[i]) = [0, 1, 0, 0, 1, 0, 0, 1, 0]
Arrays.toString(cheeseMap[i]) = [0, 1, 0, 1, 1, 1, 0, 1, 0]
Arrays.toString(cheeseMap[i]) = [0, 0, 0, 0, 0, 0, 0, 0, 0]
Arrays.toString(cheeseMap[i]) = [0, 0, 0, 0, 0, 0, 0, 0, 0]