백준 2573번 빙산 Java

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

문제

---

생각하기

---

동작

결과

코드

---

import java.io.*;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[][] board, boardClone;
    private static boolean[][] isVisited;
    private static final int[] dirX = {-1, 0, 1, 0}; // 상 우 하 좌
    private static final int[] dirY = {0, 1, 0, -1};

    private static class Coordinate {
        int x;
        int y;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } // End of Coordinate class


    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();
        
        int year = 0;
        a:
        for (; ; ) {
            int count = 0;
            isVisited = new boolean[N][M];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (isVisited[i][j] || board[i][j] == 0) continue;

                    if (count == 1) {
                        // 빙하가 한번 녹았는데, 다시 녹는과정이 생김.(덩어리 분리)
                        break a;
                    }

                    BFS(i, j);
                    count++;
                }
            }

            if (count == 0) {
                // 빙하가 하나도 녹지 않음.
                year = 0;
                break;
            }

            copy();
            year++;
        }

        sb.append(year);
        return sb.toString();
    } // End of solve()

    private static void BFS(int startX, int startY) {
        ArrayDeque<Coordinate> que = new ArrayDeque<>();
        que.offer(new Coordinate(startX, startY));
        isVisited[startX][startY] = true;

        while (!que.isEmpty()) {
            Coordinate cur = que.poll();

            int count = 0;
            for (int i = 0; i < 4; i++) {
                int nX = dirX[i] + cur.x;
                int nY = dirY[i] + cur.y;

                if (nX >= 0 && nX < N && nY >= 0 && nY < M && board[nX][nY] == 0) count++;
                if (!check(nX, nY)) continue;

                que.offer(new Coordinate(nX, nY));
                isVisited[nX][nY] = true;
            }

            boardClone[cur.x][cur.y] -= count;
            if (boardClone[cur.x][cur.y] < 0) {
                boardClone[cur.x][cur.y] = 0;
            }
        }

    } // End of BFS()

    private static boolean check(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M && board[x][y] > 0 && !isVisited[x][y];
    } // End of check()

    private static void copy() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                board[i][j] = boardClone[i][j];
            }
        }
    } // End of copy()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        boardClone = 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());
                boardClone[i][j] = board[i][j];
            }
        }

    } // End of input()
} // End of Main class