[BOJ] 2638: 치즈 (JAVA)

문제

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

 

여담

일루미네이션 문제와 치즈 문제와 비슷하다고 느꼈다. 그래서 "중간에 공간이 뻥 뚫린 것을 제외하고 탐색할 때는 역으로 생각을 하자!"라고 외웠던 것을 바탕으로 문제를 풀었다. 바깥에서부터 탐색을 할 수도 있다는 것을 기억하자!

 

풀이

이 문제는 일루미네이션 문제와 치즈 문제와 푸는 방식이 동일하다. 즉, 역으로 생각해서 밖에서부터 탐색을 수행해야 한다.

 

치즈의 4변 중에서 적어도 2변 이상이 공기와 접촉하면 해당 치즈는 녹게 된다. 이때, 치즈 내부에 있는 공간은 외부와 접촉하지 않으며 녹지 않는다. 

 

즉, 치즈 외부에 있는 공기와 접촉할 때만 치즈가 녹는다. 따라서 치즈(=회색 부분)를 탐색하는 것이 아니라, 치즈가 없는 부분(=흰색 부분)을 탐색해야 외부 공기와 접촉하는 치즈만 녹게 된다. 

 

문제에서 "모눈종이의 가장자리에는 치즈가 놓이지 않는 것으로 가정한다."라는 문구가 주어지므로, 항상 (0, 0)에서 BFS 탐색을 진행하면 된다.

 

그 이후 녹는 치즈들을 구하기 위해 모든 치즈가 녹을 때까지 다음 과정을 반복하면 된다.

1. 상하좌우로 BFS 탐색하기 (상하좌우)
   
   • 탐색한 칸에 치즈가 있는 경우
     • 공기와 접촉한 수를 저장하는 배열(melt)의 값을 1 증가시키기
   • 탐색한 칸에 치즈가 없는 경우 
     • 큐에 넣기
2. 2변 이상이 공기와 접촉한 치즈 녹이기
3. 모든 치즈가 녹지 않았다면 1번과 2번 과정 반복하기

 

코드

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

public class Main {
    static int N, M;
    static boolean[][] cheese;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cheese = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                cheese[i][j] = Integer.parseInt(st.nextToken()) == 1; // 0: false, 1: true
            }
        }

        int time = 0;
        while (!isMelt()) { // 다 녹으면 true 반환, 덜 녹으면 false 반환
            visited = new boolean[N][M];
            bfs();
            time++;
        }
        System.out.println(time);
    }

     static void bfs() {
         Queue<Pos> queue = new LinkedList<>();
         queue.offer(new Pos(0, 0));
         visited[0][0] = true;

         int[][] melt = new int[N][M];
         int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
         while (!queue.isEmpty()) {
             Pos pos = queue.poll();

             for (int i = 0; i < 4; i++) {
                 int nx = pos.x + move[i][0];
                 int ny = pos.y + move[i][1];
                 if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) {
                     continue;
                 }

                 // 치즈가 있는 칸인 경우
                 if (cheese[nx][ny]) {
                     // 공기와 맞닿으므로 1 증가
                     melt[nx][ny]++;
                 } else { // 치즈가 없는 칸인 경우
                     // 큐에 넣기
                     queue.offer(new Pos(nx, ny));
                     visited[nx][ny] = true;
                 }
             }
         }

         // 4변 중에서 2변 이상이 공기와 접촉한 경우, 치즈가 녹음
         for (int i = 0; i < N; i++) {
             for (int j = 0; j < M; j++) {
                 if (melt[i][j] >= 2) {
                     cheese[i][j] = false;
                 }
             }
         }
    }

    // 치즈가 다 녹았는지 확인하기
    static boolean isMelt() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 아직 치즈가 덜 녹은 경우
                if (cheese[i][j]) return false;
            }
        }
        // 치즈가 다 녹은 경우
        return true;
    }

    static class Pos {
        int x, y;

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

---