문제

풀이 과정

요약

BFS() 활용 문제.
공기랑 접촉한 바깥족 치즈와 안쪽 치즈를 어떻게 분류하는 가가 중요하다.

상세

1. 먼저 입력을 받는다. cnt 를 선언하여, 치즈의 총 갯수를 미리 세어둔다. 탐색을 통해, 공기와 접촉한 치즈가 사라질 때 마다, 총 치즈에서 한 개씩 빼기 위해서이다.

2. 공기를 기준으로 탐색한다. 치즈를 기준으로 탐색을 하게 되면, 정해야 할 경우의 수가 많다.

   • 만약 현재 좌표가 공기인데, 다음으로 이동하는 곳이 치즈 인경우, 그곳이 공기와 접촉하고 있는 바깥쪽 치즈이다. 공기와 접촉한 치즈를 0 으로 바꾸고 방문처리한다.
   • 만약 현재가 공기인데, 다음으로 이동하는 곳도 공기라면 다음 탐색을 위해, 방문처리 후 Queue 에 집어 넣어준다.

3. 2의 과정을 모든 치즈 갯수가 0이 될 때 까지 반복한다. 치즈 갯수가 아직 0이 아니라면, 마지막 남은 치즈 갯수를 저장하기 위해 ans 에 cnt 값을 넣어준다. 또한 시간을 의미하는 hour 를 증가시켜준다.

4. 치즈 갯수가 0이 되었을 때 hour 와 ans 를 출력해주면 된다.

정답

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

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int N, M;
    static int cnt, hour, ans = 0;
    static final int[] dr = new int[]{-1, 0, 1, 0};
    static final int[] dc = new int[]{0, -1, 0, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        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) cnt++;
            }
        }

        while (true) {
            if (cnt == 0) {
                System.out.println(hour);
                System.out.println(ans);
                break;
            } else ans = cnt;

            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{0, 0});
            visited = new boolean[N][M];
            visited[0][0] = true;
            hour++;

            while (!q.isEmpty()) {
                int[] curr = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = curr[0] + dr[d];
                    int nc = curr[1] + dc[d];

                    if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;

                    if (visited[nr][nc]) continue;

                    visited[nr][nc] = true;
                    if (map[nr][nc] == 1) {
                        cnt--;
                        map[nr][nc] = 0;
                    } else q.add(new int[]{nr, nc});

                }
            }
        }
    }
}