백준 2636 치즈

import java.util.*;
import java.io.*;
public class Main {
	static int [][] dirs = { {-1,0},{1,0},{0,1},{0,-1}};
	static int N,M;
	static int [][] map;
	static boolean[][] v;
	public static void main(String[] args) throws IOException {
		BufferedReader br;
		br = new BufferedReader(new InputStreamReader(System.in)); 
//		br = new BufferedReader(new StringReader(src));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N= Integer.parseInt(st.nextToken());
		M= Integer.parseInt(st.nextToken());
		map=new int[N][M];
		v=new boolean[N][M];
		
		int oneCnt=0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
					oneCnt++;
				}
			}
		}
		
		int beforeCnt=0;
		int time=0;
		while(oneCnt>0) {
			for (int i = 0; i < v.length; i++) {
				Arrays.fill(v[i], false);// 이전 공기도 false로 바꾼다 
			}
			bfs(); //공기 칠하기 공기는 true;
			
			//공기중에 인접한 치즈 고르기 v : true
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(v[i][j]) continue;
					if(map[i][j]==0) continue;
					for (int d = 0; d < dirs.length; d++) {
						int x =i+dirs[d][0];
						int y =j+dirs[d][1];
						if(map[x][y]==0 && v[x][y]) { //인접한 면중 공기가 있다!
							v[i][j]=true; //없앨 것이다.
							break; // 사방탐색 관둠 없앨꺼임.
						}
					}
				}
			}
			
			
			//치즈를 없애자
			beforeCnt =oneCnt;// 없애기 이전의 치즈 갯수 
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j]==1 && v[i][j]) {
						map[i][j]=0; //치즈 없앰
						oneCnt--; //생존 치즈갯수 감소
					}
				}
			}
			time++;
			
		}//while 
		
		System.out.println(time+"\n"+beforeCnt);
		
	
		
		
		
	}// main
	private static void bfs() {
		Queue<Loc> q= new LinkedList<>();
		q.offer(new Loc(0,0));
		while(!q.isEmpty()) {
			Loc air = q.poll();
			v[air.x][air.y]=true; // 공기는 true
			for (int d = 0; d < dirs.length; d++) {
				int x =air.x +dirs[d][0];
				int y =air.y +dirs[d][1];
				if(!isIn(x,y)) continue;
				if(v[x][y]) continue;
				if(map[x][y]==1) continue;
				
				v[x][y]=true;
				q.offer(new Loc(x,y));
					
			}
		}
		
	}
	private static boolean isIn(int x, int y) {
		return 0<=x && x<N && 0<=y && y<M ;
	}
	static class Loc{
		int x,y;

		public Loc(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	
}//class