BOJ (Java) 2638번: 치즈

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

---

풀이

bfs로 탐색하며 풀었다.

이 때 치즈로부터 탐색하는 게 아닌, 공기를 탐색했다.

현재 셀이 공기일 때 주위에 치즈가 있는지 확인, 있다면 공기와 맞닿은 횟수를 저장해둔다.

탐색 중에 치즈를 녹인다면 다른 곳을 탐색할 때 영향을 미치므로 이를 저장해두었다가 마지막에 한 번에 바꿔줬다.

이 때 플래그를 사용해 녹은 치즈가 없다면 현재까지 측정한 시간을 반환한다.

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    private static int[][] map;
    private static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s[] = bf.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            s = bf.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }

        // 치즈가 녹는 동안의 시간 구하기
        int time = 0;
        while (isMelted()) {
            time++;
        }
        System.out.println(time);
    }

    private static boolean isMelted() {
        int[][] air = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        int[][] mv = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        Queue<Coordinate> q = new LinkedList<>();

        // bfs 탐색, 이 때 공기를 탐색
        q.add(new Coordinate(0, 0));
        visited[0][0] = true;
        while (!q.isEmpty()) {
            Coordinate now = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = now.r + mv[i][0];
                int nc = now.c + mv[i][1];
                if (nr < 0 || nc < 0 || n <= nr || m <= nc
                        || visited[nr][nc] || map[nr][nc] == 1) continue;

                // 아직 방문하지 않은 공기 영역이면 큐에 저장
                visited[nr][nc] = true;
                q.add(new Coordinate(nr, nc));

                // 현재 위치에서 치즈가 맞닿아 있다면 공기와 맞닿은 부분++
                for (int j = 0; j < 4; j++) {
                    int nnr = nr + mv[j][0];
                    int nnc = nc + mv[j][1];
                    if (nnr < 0 || nnc < 0 || n <= nnr || m <= nnc
                            || visited[nnr][nnc] || map[nnr][nnc] == 0) continue;
                    air[nnr][nnc]++;
                }
            }
        }

        boolean isChanged = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // 공기와 맞닿은 부분이 2군데 이상이라면 녹임
                if (air[i][j] >= 2) {
                    map[i][j] = 0;
                    isChanged = true;
                }
            }
        }
        return isChanged;
    }

    // 좌표계
    private static class Coordinate {
        int r;
        int c;

        public Coordinate(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

}