[백준] 2636번 치즈 (gold 4

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

class Point{
    int x;
    int y;
    int hour;
    public Point(int x, int y, int hour){
        this.x=x;
        this.y=y;
        this.hour=hour;
    }
}
public class Main{
    static int[] numx={-1,1,0,0};
    static int[] numy={0,0,-1,1};
    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        int[][] map=new int[n+1][m+1];
        int empty=0;

        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                int t=Integer.valueOf(st.nextToken());
                map[i][j]= t==1 ? -2 : 0;
                empty= t==0 ? empty+1 : empty;
            }
        }

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1 ,Point o2){
                return o1.hour-o2.hour;
            }
        });

        boolean[][] visit=new boolean[n+1][m+1];
        que.offer(new Point(1,1,0));
        visit[1][1]=true;

        int min=Integer.MIN_VALUE;
        int width=0;

        while(!que.isEmpty()){
            if(empty==n*m){
                break;
            }
            //비게되는 칸이 총칸수이면 다 녹은것
            
            Point temp=que.poll();
            for(int i=0; i<4; i++){
                int ty=temp.y+numy[i];
                int tx=temp.x+numx[i];

                if(tx<1 || tx>m || ty<1 || ty>n || visit[ty][tx]){
                    continue;
                }
                visit[ty][tx]=true;
                int v=map[ty][tx];
                //치즈가 있으면 녹임. 
                //마지막 시간을 체크하면서, 마지막일때의 치즈 넓이를 더함
                //치즈가 녹은건 해당시간+1 시간이므로, 이를 적용하여 que.offer
                if(v==-2){
                    map[ty][tx]=temp.hour+1;
                    if(min<map[ty][tx]){
                        width=1;
                        min=map[ty][tx];
                    }
                    else{
                        width++;
                    }
                    que.offer(new Point(tx,ty,temp.hour+1));
                    empty++;
                }
                //만약 안에 막혀있던 공간일 경우. 치즈가 녹으면서 뚫릴때
                //시간설정의 문제가 발생.
                //이때 우선순위큐를 이용했기에 최저시간에서의 빈공간 접촉의 케이스가 발생되므로.
                //해당 빈공간들은 temp.hour를 적용하면됨.
                //이때 마지막 치즈 넓이를 구할때 temp.hour로 설정한 중간값은 영향이 없음
                //왜냐하면 치즈는 결국 temp.hour+1가 되므로 어떠한 temp.hour를 여기서 적용하더라도
                //녹인 치즈에서 더이상 녹이지 않으면, temp.hour+1+1의 상황 발생 x
                else if(v==0 && temp.hour>0){
                    map[ty][tx]=temp.hour;
                    que.offer(new Point(tx,ty ,temp.hour));
                }
                //만약 해당시간과 동일한 칸을 만날 경우는 넓이탐색에서 같은 시간대에 
                //해당하는 빈간이므로 큐에 넣어주기만 하면서 이 영역들에서의 치즈 녹이기 활동을 
                //전개해감
                else if(v==temp.hour){
                    que.offer(new Point(tx,ty, temp.hour));
                }

            }

        }

        bw.write(min+"\n");
        bw.write(width+"");
        bw.flush();

    }
}