[정올 1870] 치즈 - JAVA

문제 링크

문제 정의

• $N * M$의 모눈종이가 주어지고 위에 얆은 치즈가 존재
• 0은 공기 1은 치즈
• $N*M$의 바깥 영역에는 치즈가 존재하지 않음
• 치즈는 외부 공기와 2변 이상이 접촉해야 녹는다 (1시간 소요)

모눈종이 위의 치즈가 모두 녹아 없어지는데 걸리는 시간을 출력

---

접근 방법

외부 공기와 내부 공기

이 문제에서의 가장 큰 함정입니다.
저는 처음에 단순히 공기인 0이 2변에 존재하면 되는 것으로 파악해서
문제를 해당 조건에 맞게 코드를 구현했지만
문제는 외부 공기와 내부 공기라는 개념이 존재했습니다.

외부 공기는 $N*M$의 테두리 부분의 공기를 말하고
내부 공기는 치즈로 둘러싸여 공기이지만 바깥쪽으로 공기가 통하지 않아 조건에 해당하지 않습니다.

그렇기 때문에 시간대별 녹는 치즈에 따라
외부 공기로 바뀌는 내부 공기가 존재하는지 계속해서 체킹해야 합니다.

---

초기화

입력에 대한 초기화를 진행한 후 가장 먼저 해야할 것은
초기 시점에서 공기를 외부 공기와 내부 공기로 구분하는 것입니다.

그렇기 떄문에 $(0,0)$좌표는 항상 공기만 존재하고 외부 공기이기 때문에
$(0,0)$에서 dfs를 수행해서 외부 공기를 -1로 변경해준다면
외부 공기와 내부 공기를 분리할 수 있습니다.

• 외부 공기: -1
• 내부 공기: 0
• 치즈: 1

저는 isMeltable 이라는 메서드를 구현했습니다.
현재 시점에 치즈가 녹을 수 있는지 여부를 판별할 수 있는 메서드입니다.
이 메서드를 통해 전체 영역에 대해 초기 시점에 공기 접촉이 2면 이상인 치즈들을
큐에 넣는 작업을 수행했습니다.

---

BFS 수행

이제 BFS를 수행해야 합니다.

시간별 BFS를 수행하기 위해
큐 사이즈를 활용한 이중 while문을 사용한 BFS를 구현했습니다.

그리고 현재좌표로부터 상하좌우로 이동해서 area[ny][nx] == 0인 경우에는
내부 공기가 외부 공기로 바뀌는 구간이기 때문에
dfs를 수행해서 내부 공기를 외부 공기로 변환하도록 로직을 설계했습니다.

그 이후 내부 공기의 처리 로직이 완료되었다면
전체 for 문을 수행해서 다음 녹을 치즈를 다시 큐에 넣는 작업을 수행했습니다.

만일 넣은 큐가 없다면 모든 치즈가 녹은 것이므로 time을 출력하고 문제를 해결하게 됩니다.

---

회고

이 문제를 풀면서 하나 아쉬운 점은
녹을 치즈들을 큐에서 하나씩 꺼내 처리한 후
다음 시간에 녹을 치즈들을 큐에 저장하는 과정에서
모든 $N*M$ 영역을 다시 탐색해야하는 문제점이 존재했습니다.

물론 시간을 들이면 최적화가 가능하겠지만
PCCP를 준비하는 현재로서는
최적화를 위해 별도로 코드를 작성하지 않으려고 합니다.

예를 들면
candidate 큐를 생성해서 현재 녹는 치즈의 상하좌우에 치즈가 존재한다면
해당 치즈를 후보군으로 큐에 저장하고
또 내부 공기가 외부 공기로 변하는 시점에 DFS를 수행할 떄
현재 좌표의 상하좌우에 녹지 않은 치즈가 존재하는 경우
후보군으로 candidate 큐에 저장하는 방식 등을 고려해봤습니다.
추후 시간이 남는다면 최적화까지 고려해서 코드를 작성해볼 예정입니다.

---

코드

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

class Node {
    int y;
    int x;

    public Node (int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static StringTokenizer st;
    static int[][] area;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int N;
    static int M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        dfs(0, 0, -1);
        System.out.println(bfs());
    }

    static int bfs() {
        ArrayDeque<Node> q = new ArrayDeque<>();
        ArrayDeque<Node> candidate = new ArrayDeque<>();

        getCurrentMelt(q);


        if (q.isEmpty()) return 0;

        int time = 0;
        while (true) {
            int size = q.size();

            while (size-- > 0) {
                Node node = q.poll();
                int y = node.y;
                int x = node.x;

                for (int d = 0; d < 4; d++) {
                    int ny = y + dy[d];
                    int nx = x + dx[d];

                    if (outbound(ny, nx) || area[ny][nx] == -1) continue;

                    if (area[ny][nx] == 0) dfs(ny, nx, -1);
                    else candidate.offer(new Node(ny, nx));
                }

                area[y][x] = -1;
            }

            while(!candidate.isEmpty()) {
                Node tmp = candidate.poll();
                if (isMeltable(tmp.y, tmp.x)) q.offer(tmp);
            }

            time++;
            if (q.isEmpty()) return time;
        }
    }

    private static void getCurrentMelt(ArrayDeque<Node> q) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] == 1 && isMeltable(i, j)) {
                    q.offer(new Node(i, j));
                }
            }
        }
    }

    static void dfs(int y, int x, int status) {
        area[y][x] = status;

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];

            if (outbound(ny, nx) || area[ny][nx] != 0) continue;

            dfs(ny, nx, status);
        }
    }

    static boolean outbound(int y, int x) {
        return y < 0 || y >= N || x < 0 || x >= M;
    }

    static boolean isMeltable(int y, int x) {
        int count = 0;

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];

            if (outbound(ny, nx) || area[ny][nx] != -1) continue;

            if (++count >= 2) return true;
        }

        return false;
    }
}