[백준] 2636번 : 치즈 - 자바(JAVA)

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

2636번: 치즈

 

문제 해석

정사각형 칸으로 이루어진 보드가 존재합니다.

그 위에 회색으로 표시된 부분은 치즈를 의미합니다.

원래 치즈 모양

치즈는 공기 중에 놓으면 녹게 되며 한 시간이 지나면 녹게 됩니다.

테두리 부분인 c부분이 한 시간이 지나면 녹게 되며 다음과 같은 그림이 됩니다.

한 시간 후의 치즈 모양

두 시간 후의 치즈 모양

 

이때 치즈가 모두 녹아 없어지는데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 구하세요

 

문제 풀이 전 설계

공기와 맞닿는 부분은 항상 치즈의 테두리입니다.

처음에는 치즈의 테두리부분을 하나 선정하여 BFS로 테두리를 쫙 탐색하려고 했으나 C가 중간에 끊어지는 부분이 있어 불가능해 보였습니다.

 

치즈가 안에 있는것을 어떻게 확인할 수 있을까요?

바로 치즈를 기준으로 위, 아래, 왼쪽, 오른쪽을 배열의 끝까지 탐색하여 주변 모든 칸에 치즈가 존재하면 이는 안에 있는 치즈이며 그렇지 않으면 이는 테두리에 존재하는 치즈입니다.

 

위의 사항은 반례가 존재합니다.

동그라미 쳐진 부분은 상하좌우에서 치즈를 발견할 수 있으나 이는 테두리에 존재하는 치즈입니다.

 

보드의 가장자리에는 치즈가 올 수 없다는 것이 문제의 핵심 같습니다.

항상(0,0)에는 빈칸이올테고 해당 칸을 기준으로 BFS를 쭉 돌리게 되면 외부 공기를 순회하며 맞닿아있는 외부 치즈를 모두 구할 수 있습니다.

 

이것을 치즈가 모두 없어질때까지 반복하면 끝입니다.

 

코드

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

public class Main_2636_치즈 {
    public static int N, M, remainCheeseCount, cnt, time;
    public static int[][] board;
    public static boolean[][] visited;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    static class Pos {
        int y;
        int x;

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

    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());
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1)
                    remainCheeseCount++;
            }
        }
        while (remainCheeseCount != 0) {
            time++;
            cnt = remainCheeseCount;
            meltingCheese();
        }
        System.out.println(time);
        System.out.println(cnt);
    }

    public static void meltingCheese() {
        Queue<Pos> que = new LinkedList<>();
        que.offer(new Pos(0, 0));
        visited = new boolean[N][M];
        visited[0][0] = true;
        while (!que.isEmpty()) {
            Pos currentPos = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = currentPos.x + dx[i];
                int ny = currentPos.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
                if (board[nx][ny] == 1) {
                    remainCheeseCount--;
                    board[nx][ny] = 0;
                } else if (board[nx][ny] == 0) {
                    que.offer(new Pos(ny, nx));
                }
                visited[nx][ny] = true;
            }
        }
    }
}