[백준] 2636 치즈

문제 출처: www.acmicpc.net/problem/2636

2636번: 치즈

: 치즈가 가장자리부터 서서히 녹게 되고 모두 녹는데 걸리는 시간과 모두 녹기 직전의 치즈 영역의 수를 출력해야한다.

: 치즈가 녹는 방식은 가장자리부터 녹게되는데 치즈 중간에 있는 구멍에 닿아 있는 부분은 녹지 않는다.

: 따라서 온전히 바깥에 있는 부분부터 녹여야 한다. 

: bfs 함수를 만들어 주는데 이 함수는 치즈를 만날경우 0으로 바꿔 녹이기만 하고, 공기를 만날경우 큐에 넣도록 한다.

: 자연스럽게 치즈는 가장자리부터 0이 될 수 있게 된다. 

: 또한 방문처리를 하면서 가기 때문에 중복으로 가지 않아 전체를 한번 통과하면 시간을 증가시키고, 그 때 남은 치즈의 개수를 저장해 놓는다.

: 이러한 과정을 반복하다가 치즈의 개수가 0이 되면 중단하도록 한다.

: 중간중간 남은 치즈의 개수를 세어줄 수 있지만, 그렇게 하기 보다는 처음 입력값을 받을 때 전체 치즈 개수를 저장해 놓고 녹을 때마다 마이너스 해주면 바로바로 그 값을 계산해 나갈 수 있다.

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

public class 치즈 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int R, C;
	static int cheeseCnt;
	static int[][] map;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static class Point{
		int r, c;
		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		
		for(int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) cheeseCnt++;
			}
		}
		int res = 0, time = 0;
		
		while(cheeseCnt != 0) {
			time++;
			res = cheeseCnt;
			bfs(0,0);
		}
		System.out.println(time);
		System.out.println(res);
	}
	static int cnt = 0;
	private static void bfs(int r, int c) {
		Queue<Point> q = new LinkedList<>();
		boolean[][] v= new boolean[R][C];
		q.offer(new Point(r, c));
		v[r][c] = true;
		while(!q.isEmpty()) {
			Point cur = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				if(nr < 0 || nr >= R || nc < 0 || nc >= C  ||v[nr][nc]) continue;
				if(map[nr][nc] == 1) {
					cheeseCnt--;
					map[nr][nc] = 0;
				}else {
					q.offer(new Point(nr, nc));
				}
				v[nr][nc] =true;	
			}
			
		}
	}
}