[JAVA] 2638. 치즈

백준에 비슷한 문제가 있다.

이 문제를 푼 경험을 통해 조금더 쉽게 할 수 있었다.

2636번: 치즈

 

처음 가장 고민한 부분은 안쪽 치즈를 녹이지 않고 밖에 존재하는 외부 치즈만 녹이는 법을 어떻게 해야하는지 고민을 했었다.

우리는 항상 빈곳이 아닌 곳을 방문처리하고, bfs를 하였는데 이 경우는 반대로 치즈가 존재하지 않은 곳을 시작으로 계속해서 0인 곳을 큐로 넣고 연산을 시작하면, 놀랍게도 안쪽의 치즈는 영향을 받지 않게 된다.

 

계속해서 0인 곳만을 큐에 넣기 때문에 밖에서 외부의 치즈 방어막을 걸리면 큐에 추가는 그곳에서 끝이 나기 때문에 당연히 안쪽 치즈로 올 수 있는 경로가 막히게 되기 때문이다.

 

문제에서 치즈는 2번의 외부와의 접촉이 존재해야 녹게 된다.

그 부분을 처리하기 위해 1인 치즈를 2로 변경하여 2번의 외부 접촉이 되면 0이 되어 치즈가 녹도록 하는 방식을 가졌으며, 방문처리는 0일 경우와 모든 치즈가 녹아 0이 될 경우만 방문처리를 하였다.

 

즉, 2에서 1로 되어 1번 외부와의 접촉이 된 치즈는 방문처리를 하지 않았다.

그 이유는 2번의 접촉이 되어야 하는데 1번에 방문처리를 하게 되면 2번째의 외부 접촉이 되지 않기 때문이고, 2인 치즈가 2번의 외부처리로 0이 되면 방문처리를 한 이유는 0이 될 때 방문처리를 하지 않으면 다른 외부에서 해당 자리로 오게 되면 현재 시간에 녹아 0이 된 곳을 외부로 다시 넣어 다음 시간에 해야할 일들을 진행하기 때문에 방문처리를 하여 시간이 경과된 다음 연산에 0인 외부로 역할을 하게 하기 위해서이다.

 

그리고 마지막으로 전체적인 연산이 한번씩 끝나면 2인 치즈 중 한번의 외부접촉으로 1이 된 치즈가 존재한다.

그 치즈는 다음 연산에서도 2번의 접촉이 되어야만 녹기 때문에 다시 1을 2로 변경하여 완전한 치즈로 다시 변경 후 새로운 연산을 시작해주어야 한다.

 

 

 

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B_2638_치즈 { 
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][M];
        int cheeseCnt = 0; // 시작 치즈의 개수
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    cheeseCnt++;
                }
            }
        }
        int startY = 0; // 첫 시작 지점 - 0인 곳
        int startX = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    startY = i;
                    startX = j;
                    break;
                }
            }
        }
        int result = bfs(cheeseCnt, startY, startX, N, M, arr);
        System.out.println(result);
    }
 
    private static int bfs(int cheeseCnt, int startY, int startX, int N, int M, int[][] arr) {
        int time = 0; // 결과값
        while (cheeseCnt > 0) { // 치즈가 모두 녹아없어질 때까지
            time++; // 시간 경과
            
            for (int i = 0; i < N; i++) { // 2번 이상의 실내 접촉 - 1로 줄어든 치즈 다시 원상 복귀
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == 1) {
                        arr[i][j] = 2;
                    }
                }
            }
            int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
            Queue<Node> q = new LinkedList<>();
            boolean[][] visited = new boolean[N][M];
            visited[startY][startX] = true;
            q.offer(new Node(startY, startX));
            
            while (!q.isEmpty()) {
                Node now = q.poll();
                int y = now.y;
                int x = now.x;
                for (int i = 0; i < 4; i++) {
                    int my = y + dir[i][0];
                    int mx = x + dir[i][1];
                    if (my < 0 || mx < 0 || my >= N || mx >= M || visited[my][mx])
                        continue;
                    if (arr[my][mx] == 0) { // 치즈가 없으면 큐에 넣기
                        visited[my][mx] = true;
                        q.offer(new Node(my, mx));
                    } else {// 녹아내림
                        arr[my][mx]--;
                        if (arr[my][mx] == 0) { // 다 녹아내리면 방문처리 - 2번 모두를 방문해야하므로 1번째에는 방문처리를 하지 않음.
                            cheeseCnt--;
                            visited[my][mx] = true;
                        }
                    }
                }
            }
        }
        return time;
    }
 
    static class Node {
        int y, x;
 
        public Node(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
    }
}