골드4 - 백준 2638 치즈

백준 2638 치즈

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

접근방법

이 문제는 바깥 공기와 2면 이상 닿는 치즈를 단계적으로 제거해나가면서 치즈가 다 없어질 때까지 걸리는 시간을 구하는 문제였다. 치즈의 안쪽은 치즈가 제거되지 않아야 했다. 따라서 문제 조건에서 가장 가장자리는 항상 비어있기 때문에, 0,0 위치에서 BFS로 2면 이상 닿는 치즈들을 차례대로 처리해주었다.

풀이

while문으로 모든 치즈가 사라질 때까지 반복해주면서 day 변수를 1씩 증가시켜주었다. 그리고 0,0을 기준으로 BFS를 시작했고 빈 공간이고 첫 방문이라면 visited배열에 1을 더해주고 다시 같은 위치가 방문되지 않게 조건을 걸어주었다. 치즈가 있다면 visited배열이 2미만이라면 방문해주고 방문 회수가 2가 되면 temp 백터에 넣어주어 제거할 치즈들을 저장해주었다.
BFS가 종료되면 temp에 저장했던 치즈들을 전부 제거하고 board_cnt 함수를 통해 빈 공간의 개수를 확인해주고 전부 비었다면 반복문을 종료하고 day 변수를 출력해주었다.

코드

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

public class Main {

    private static int[][] board;
    private static int[][] visited;
    private static Queue<Pair> air = new LinkedList<>();
    private static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        final int N = Integer.parseInt(input[0]), M = Integer.parseInt(input[1]);
        board = new int[N][M];
        visited = new int[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]);
                visited[i][j] = 0;
            }
        }

        int day = 0;

        while(true) {

            day++;
            //System.out.println(day);
            Queue<Pair> temp = new LinkedList<>();

            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++)
                    visited[i][j] = 0;
            }

            air.add(new Pair(0,0));
            visited[0][0] = 1;

            while (!air.isEmpty()) {

                Pair p = air.poll();

                for (int i = 0; i < 4; i++) {
                    int nx = p.first + dir[i][0];
                    int ny = p.second + dir[i][1];

                    if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                        continue;

                    if (board[nx][ny] == 0 && visited[nx][ny] == 0) {
                        visited[nx][ny]++;
                        air.add(new Pair(nx, ny));
                    }
                    if (board[nx][ny] == 1 && visited[nx][ny] < 2) {
                        if (visited[nx][ny] == 1) {
                            temp.add(new Pair(nx, ny));
                        }
                        visited[nx][ny]++;
                    }
                }
            }

            while(!temp.isEmpty()) {
                Pair p = temp.poll();
                board[p.first][p.second] = 0;
            }

            if(board_cnt(N, M))
                break;
        }

        System.out.println(day);
    }

    private static boolean board_cnt(int N, int M) {

        int cnt = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(board[i][j] == 0)
                    cnt++;
            }
        }
        return cnt == N * M;
    }

    private static class Pair {
        public int first;
        public int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}