[BOJ 2636]チーズ(Java)

質問する
下図1に示すように、正方形の格子からなる正方形の板があり、その上に薄いチーズ(灰色の部分)が置かれています.板の縁(<図1>では、四角形のXの部分)にはチーズが入っておらず、チーズには1つ以上の穴が開いていてもよい.
これらのチーズを空気中に入れると溶け、空気に触れる車両は1時間後に溶けます.チーズの穴には空気が入っていませんが、穴を囲むチーズが溶けて穴が開くと空気が穴に入ります.<図1>に示すように、チーズ孔を囲むチーズは溶けず、図2>に示すように、「c」と表記された部分だけが1時間後に溶けて消える.

あと1時間で<図2>の「c」で表される部分は<図3>に示すように溶けて消えてしまいます.


<図3>チーズが2時間後の様子で、残りの破片はあと1時間で全部溶けてしまいました.そのため、初めてチーズが全部溶けて消えるまで3時間かかります.<図3>に示すように、チーズは融解中にいくつかに分けることができる.
矩形板の大きさとチーズが板に置かれたとき、空気中のチーズがすべて溶けるのに要する時間と、すべて溶ける1時間前にチーズの破片が残った格子数を入力するプログラムを作成します.
入力
最初の行は、矩形板の縦横長が正の整数であることを示します.縦横の長さは最大100です.板上の各横線の形状は、上から下へ順に2行目から最後の行までです.チーズのない格子は0で、チーズのある格子は1で、数字の間にスペースがあります.
しゅつりょく
1行目はチーズが全部溶けて消えるまでの時間を出力し、2行目は全部溶ける1時間前に置いたチーズの破片の格子数を出力します.
方法

問題の要求に従って大幅に分離した.

で与えられた空間にチーズがあるかどうかを判断します.チーズがある場合は、既存のチーズの数を保存してください.

チーズが溶けました.

が溶けて消えた空間には空気が満ちていた.

最初の条件と2番目の条件「所定の空間にチーズが存在するかどうかを決定し、チーズの数を保存する」で、すべての場所に移動し、チーズの数を返す関数(getCheescnt()の値をlastCheeseに格納します.

2つ目の条件「チーズが溶ける」すべての場所に移動して実行します.この場所がチーズの場合、上、下、左、右の[空気](Air)の値を0に設定して溶かします.次にairDequeに位置を追加し、次の呼び出しのfillAir()から実際の空気に変換できます.

3つ目の条件は「溶けて消えた空間に空気を充填する」ことです.実施する.2つ目の条件では、融解領域が現れるたびにairDequeに位置を保存します.BFSに移動して空気を充填し、空気の実際のアレイに表示します.

上記の条件を繰り返し、チーズが消えるまで時間と最後のチーズの数を記録します.

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

public class Cheese_2636 {

    static int n, m;
    static int[][] board;
    static boolean[][] air;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static ArrayDeque<Node> airDeque = new ArrayDeque<>();

    static class Node {
        int x;
        int y;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        board = new int[n][m];
        air = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(input[j]);
            }
        }

        // air 배열의 초기 구역 입력
        airDeque.offerLast(new Node(0, 0));
        fillAir();

        int time = 0;
        int lastCheese = 0;
        int cheese;

        // 치즈가 0개가 될 때 까지 순차적으로 진행합니다.
        // 1. lastCheese 에 현재 board에 있는 모든 치즈의 개수를 저장합니다.
        // 2. cheeseMelt() 를 호출해 치즈를 녹입니다.
        // 3. fillAir() 를 호출해 공기를 채웁니다.
        // 4. time++ 로 지나온 시간을 추가합니다.
        while ((cheese = getCheeseCnt()) > 0) {
            lastCheese = cheese;
            cheeseMelt();
            fillAir();
            time++;
        }

        sb.append(time).append('\n').append(lastCheese);
        System.out.println(sb);
        br.close();
    }

    // 치즈가 남아있는지 확인합니다. while 문의 종료 조건을 담당합니다.
    // 마지막으로 남은 치즈를 카운팅 하기 위해 int형을 반환합니다.
    public static int getCheeseCnt() {
        int cheese = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) cheese++;
            }
        }
        return cheese;
    }

    // 모든 노드들을 개별 탐색하며 치즈를 녹입니다.
    // isMelted() 함수로 치즈가 녹을 수 있는지 판단하고 녹게되면 airDeque()를 호출해 공기로 변환합니다.
    public static void cheeseMelt() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && isMelted(i, j)) {
                    board[i][j] = 0;
                    airDeque.offerLast(new Node(i, j));
                }
            }
        }
    }

    // 공기를 채우는 함수, airDeque에 있는 값으로 BFS를 돌려 공기를 채워간다.
    public static void fillAir() {
        while (!airDeque.isEmpty()) {
            Node now = airDeque.removeFirst();
            air[now.x][now.y] = true;

            for (int i = 0; i < 4; i++) {
                int tmpx = now.x + dx[i];
                int tmpy = now.y + dy[i];
                if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < m && !air[tmpx][tmpy] && board[tmpx][tmpy] == 0) {
                    air[tmpx][tmpy] = true;
                    airDeque.offerLast(new Node(tmpx, tmpy));
                }
            }
        }
    }

    // 선택된 위치의 치즈가 녹는 치즈이면 true, 녹지 않는 치즈이면 false를 반환
    public static boolean isMelted(int x, int y) {
        boolean melt = false;
        for (int i = 0; i < 4; i++) {
            int tmpx = x + dx[i];
            int tmpy = y + dy[i];
            if (air[tmpx][tmpy]) {
                melt = true;
                break;
            }
        }
        return melt;
    }
}

結果