백준 - 2636번(치즈)

문제 출처: https://www.acmicpc.net/problem/2636

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static int[][] directions = {
            { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }
    };

    private static int[][] matrix;
    private static boolean[][] outside;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int R = Integer.parseInt(tokenizer.nextToken()); // 행
        int C = Integer.parseInt(tokenizer.nextToken()); // 열

        matrix = new int[R][C];
        int cnt = 0;
        for (int i = 0; i < R; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < C; j++) {
                matrix[i][j] = Integer.parseInt(tokenizer.nextToken());
                if (matrix[i][j] == 1) cnt++;
            }
        }

        int idx = 0;
        int ans = 0;

        while (cnt > 0) {
            outside = new boolean[R][C];

            Queue<int[]> findOutside = new ArrayDeque<>(); // 바깥 공기 찾기 BFS
            findOutside.offer(new int[] { 0, 0 });

            while (!findOutside.isEmpty()) {
                int[] curr = findOutside.poll();

                if (outside[curr[0]][curr[1]]) continue;
                
                outside[curr[0]][curr[1]] = true; // 외부공기

                for (int i = 0; i < 4; i++) {
                    int dy = curr[0] + directions[i][0];
                    int dx = curr[1] + directions[i][1];

                    if (dy >= 0 && dy < R && dx >= 0 && dx < C && matrix[dy][dx] == 0 && !outside[dy][dx]) {
                        findOutside.offer(new int[] { dy, dx });
                    }
                }
            }

            idx++;
            ans = cnt != 0 ? cnt : ans;

            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (matrix[i][j] == 1) {
                        for (int x = 0; x < 4; x++) {
                            int dy = i + directions[x][0];
                            int dx = j + directions[x][1];

                            if (outside[dy][dx]) {
                                matrix[i][j] = 0;
                                cnt--;
                                break;
                            }
                        }
                    }
                }
            }

            /*for (int[] row : matrix) System.out.println(Arrays.toString(row));
            System.out.println();*/
        }

        System.out.println(idx + "\n" + ans);
    }

}

• 문제를 접근함에 있어 여러가지 방식을 고민해 보다가 결국 답을 얻지 못해 구글링을 통해 실마리를 찾았다.
• 외부 공기와 내부 공기 처리를 두고 고민을 많이 했었는데, 4방 탐색을 통해 외부 공기의 경우 쉽게 표시를 할 수 있었다.
• BFS를 통해 외부 공기를 체크하고 하나라도 외부 공기와 접해 있는 치즈의 경우 녹는 처리를 했는데, BFS 시 중복처리를 제대로 해주지 않아 메모리 초과가 나왔었다.