2638번. 치즈

 

 

아이디어

처음에는 치즈가 존재하는 칸을 찾고 이 칸을 기준으로 인접한 4칸을 탐색한 후 빈 칸이 몇 개인가를 카운팅하는 로직을 생각했으나 치즈 내부 공간은 치즈가 녹는 데 영향을 미치지 않으므로 이 방법을 사용할 수 없었다.

 

그래서 치즈가 없는 외부에서 dfs 또는 bfs 를 수행하고 치즈로 막힌 경우 다른 경로를 찾게함으로써 치즈 외부 빈칸을 모두 탐색하는 방식을 사용했다.

 

이 때 내부 공간과 구분하기 위해 탐색된 칸의 값은 음수로 설정해주었다.

 

이렇게 외부 공간을 표시한 후 현재 치즈가 녹으면 큐에서 제거해주고 아니면 다시 큐에 추가하는 방식을 사용했고 치즈를 담은 큐에 아무것도 남지않을 때까지 반복해 시간을 구했다.

 

 

풀이코드

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

public class Main {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int N;
    static int M;

    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());

        Queue<int[]> cheese = new LinkedList<>();
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) cheese.add(new int[]{i, j});
            }
        }

        int T = 0;
        while (!cheese.isEmpty()) {
            T++;
            // melt()
            dfs(0, 0, map, T);
            melt(map, cheese);
        }

        System.out.println(T);
    }

    public static void dfs(int i, int j, int[][] map, int T) {
        map[i][j] = -T;

        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (map[nx][ny] == -T | map[nx][ny] == 1) continue;

            dfs(nx, ny, map, T);
        }
    }

    public static void melt(int[][] map, Queue<int[]> cheese) {
        int len = cheese.size();

        for (int i = 0; i < len; i++) {
            int[] now = cheese.poll();
            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                int nx = now[0] + dx[k];
                int ny = now[1] + dy[k];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (map[nx][ny] < 0) cnt++;
            }
            if (cnt >= 2) map[now[0]][now[1]] = 0;
            else cheese.add(now);
        }
    }
}