백준|2636번|치즈

문제설명
정사각형 모양의 판에 치즈가 있고 치즈의 바깥면은 1초마다 녹는다고 할 때 치즈가 모두 녹는데 걸리는 시간과 모두 녹기 한시간전에 남아있는 조각의 개수를 구하는 문제입니다.

작동 순서
1. 치즈가 들어있는 판의 크기를 입력받는다.
2. 치즈 조각들의 위치를 입력받는다.
3. 0,0부터 시작해서 바깥부분들을 탐색한다.
4. 바깥부분을 탐색하며 바깥부분과 닿은 치즈를 발견하면 그 치즈를 녹이고 치즈 개수를 --하고 임시 큐에 그 위치를 삽입한다.
5. 바깥부분을 탐색하며 치즈가 없는 다른 바깥부분을 발견하면 그 위치에서 다시 근처를 탐색한다.
6. 바깥부분을 모두 탐색하면 임시 큐에 있는 다음 시간에 녹을 치즈들의 위치를 큐에 삽입한다.
7. 4,5,6을 반복하며 치즈를 모두 녹이고 치즈가 녹기 한시간전의 치즈의 개수와 치즈가 녹는데 걸린 시간을 출력한다.

소스코드

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

public class 백준_2636번_치즈 {
    static int row, column, cheese;
    static int[][] check = {{-1, 0},{1, 0},{0,-1},{0,1}};

    static Queue<Integer> rowQueue = new LinkedList<>();
    static Queue<Integer> columnQueue = new LinkedList<>();
    static Queue<Integer> rowQueueTemp = new LinkedList<>();
    static Queue<Integer> columnQueueTemp = new LinkedList<>();

    static void checkMap(int meltingRow, int meltingColumn, int[][] map, boolean[][] visited){
        for(int i=0;i<4;i++){
            if(meltingRow+check[i][0] >=0 & meltingRow+check[i][0] <= row+1 & meltingColumn+check[i][1] >= 0 & meltingColumn+check[i][1] <= column+1){
                if(!visited[meltingRow+check[i][0]][meltingColumn+check[i][1]]){
                    if(map[meltingRow+check[i][0]][meltingColumn+check[i][1]]==1){
                        rowQueueTemp.add(meltingRow+check[i][0]);
                        columnQueueTemp.add(meltingColumn+check[i][1]);
                        map[meltingRow+check[i][0]][meltingColumn+check[i][1]]=0;
                        cheese--;
                    }
                    else{
                        rowQueue.add(meltingRow+check[i][0]);
                        columnQueue.add(meltingColumn+check[i][1]);
                    }
                    visited[meltingRow+check[i][0]][meltingColumn+check[i][1]]=true;
                }
            }
        }
    }

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

        row=Integer.parseInt(st.nextToken());
        column=Integer.parseInt(st.nextToken());

        int[][] map = new int[row+2][column+2];
        boolean[][] visited = new boolean[row+2][column+2];

        int hour=0;
        int prevCount = 0;

        for(int i=1;i<row;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<column;j++)
            {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]==1) cheese++;
            }
        }

        rowQueue.add(0);
        columnQueue.add(0);

        while(!rowQueue.isEmpty()){
            if(cheese!=0) prevCount=cheese;
            while(!rowQueue.isEmpty()){
                int meltingRow=rowQueue.poll();
                int meltingColumn=columnQueue.poll();
                checkMap(meltingRow, meltingColumn, map, visited);
            }

            while(!rowQueueTemp.isEmpty()){
                rowQueue.add(rowQueueTemp.poll());
                columnQueue.add(columnQueueTemp.poll());
            }

            hour+=1;
        }
        System.out.println(hour-1);
        System.out.println(prevCount);
    }
}