[백준] 2638번 치즈 (gold 3

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

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static int[][] map;
    static boolean[][] visit;
    static int[] numx={-1,1,0,0};
    static int[] numy={0,0,-1,1};
    static Queue<Point> que=new LinkedList<>();
    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());

        map=new int[n+2][m+2];
        visit=new boolean[n+2][m+2];
        Queue<Point> area=new LinkedList<>();
        int width=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());
                if(t==0){
                    map[i][j]=100000;
                }
                else{
                    map[i][j]=200000;
                    area.offer(new Point(j,i));
                    width++;
                }
            }
        }

        //막힌공간 제외 빈공간 초기화
        que.offer(new Point(1,1));
        check(n,m);


        //치즈 체크 만약 중간에 치즈가 뚫리는 부분의 상하좌우 중 막힌 곳이면 (1000, 막히지 않은 곳은 0으로 초기화됨)
        //함수돌려서 막힌곳 연결부분 뚫기.
        //녹은 치즈에는 time저장해서 현타임과 비교하여서 녹은 것과 정리
        int time=0;
        while(true){
            if(width==0){
                break;
            }
            time++;
            int max=area.size();
            for(int i=0; i<max; i++){
                Point temp=area.poll();
                //상하좌우 몇개 녹는지.
                int how=0;
                for(int j=0; j<4; j++){
                    int ty=temp.y+numy[j];
                    int tx=temp.x+numx[j];
                    if(tx<1 || tx>m || ty<1 || ty>n){
                        continue;
                    }
                    //몇개가 빈공간과 접하는지
                    if(map[ty][tx]<time){
                        how++;
                    }
                }
                //두개 보다 적으면 안녹음 다시 집어넣기.
                if(how<2){
                    area.offer(new Point(temp.x,temp.y));
                }
                //두개이상이면 녹는거, 전체영역 줄이고
                //언제인지 시간저장. 그리고 혹시 막힌 곳 맞닿은 곳있으면 다 넣기
                else{
                    width--;
                    map[temp.y][temp.x]=time;
                    que.offer(new Point(temp.x, temp.y));
                }
            }
            //여기서 초기화
            if(que.size()>0){
                check(n,m);
            }
        }

        bw.write(time+"");
        bw.flush();


    }


    //빈공간 체크해주기 (처음에 빈공간이랑 분리하기위해 모든 빈공간을 -1로 설정.
    //가장자리 넣어주면 막힌 곳제외 0초기화
    //막힌 곳 뚫릴때 진행하면 막혔던 곳들 연결된 부분 싹 0으로 초기화
    public static void check(int n, int m){
        Point a=que.peek();
        map[a.y][a.x]=0;
        visit[a.y][a.x]=true;
        while(!que.isEmpty()) {
            Point temp=que.poll();
            for (int i = 0; i < 4; i++) {
                int ty = temp.y + numy[i];
                int tx = temp.x + numx[i];

                if (ty < 1 || ty > n || tx < 1 || tx > m || visit[ty][tx]) {
                    continue;
                }
                if (map[ty][tx] == 100000) {
                    visit[ty][tx] = true;
                    map[ty][tx] = 0;
                    que.offer(new Point(tx, ty));
                }
            }
        }

    }
}

//초기 코드

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

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static int[][] map;
    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());

        map=new int[n+2][m+2];
        Queue<Point> area=new LinkedList<>();
        int width=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());
                if(t==0){
                    map[i][j]=100000;
                }
                else{
                    map[i][j]=200000;
                    area.offer(new Point(j,i));
                    width++;
                }
            }
        }
        Queue<Point> que=new LinkedList<>();
        que.offer(new Point(1,1));
        check(que, n,m);

        int time=0;
        int max=area.size();
        while(true){
            if(width==0){
                break;
            }
            time++;
            int end=max;
            for(int i=0; i<end; i++){
                Point p=area.poll();
                int how=0;
                for(int j=0; j<4; j++){
                    if(map[p.y+numy[j]][p.x+numx[j]]<time){
                        how++;
                    }
                }
                if(how<2){
                    area.offer(p);
                }
                else{
                    width--;
                    max--;
                    que.offer(p);
                }
            }
            if(que.size()>0){
                check(que, n,m);
            }
        }

        bw.write(time+"");
        bw.flush();


    }
    public static void check(Queue<Point> que, int n, int m){
        while(!que.isEmpty()) {
            Point p=que.poll();
            map[p.y][p.x]=0;

            for (int i = 0; i < 4; i++) {
                int ty = p.y + numy[i];
                int tx = p.x + numx[i];

                if (ty < 1 || ty > n || tx < 1 || tx > m || map[ty][tx]!=100000) {
                    continue;
                }
                if (map[ty][tx] == 100000) {
                    map[ty][tx] = 0;
                    que.offer(new Point(tx, ty));
                }
            }
        }

    }
}

//수정코드

//결과적으로 메모리 시간이 크게 단축되었다.