백준 7576 - 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_7576_토마토 {
							//상, 하, 좌, 우
	private static int[] dy = {0, 0, -1, 1};
	private static int[] dx = {-1, 1, 0, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		int M = Integer.parseInt(tk.nextToken());
		int N = Integer.parseInt(tk.nextToken());
		int count = 0;
		
		int[][] box = new int[N][M];
		
		// 다른 토마토를 익게 만들 토마토들의 위치를 저장.
		Queue<int[]> que = new ArrayDeque<int[]>();
		
		for(int i = 0; i < N; i++) {
			tk = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(tk.nextToken());
				// 1일 경우 익은 토마토가 들어있다는 말이므로 que에 담고 visited 처리 해줌.
				// 1이나 -1일 경우 익은 토마토이거나 비어있다는 의미이므로 첫날에 전부 익었는지 확인하기 위해 count를 세줌.
				if(box[i][j] == 1) {
					count++;
					que.add(new int[] {i, j});
				}else if(box[i][j] == -1) count++;
			}
		}
		
		// 만일 전부 비었거나 익은 토마토였다면 count가 N * M과 같을 것이다.
		// 이때는 0을 출력하고 종료한다.
		if(count == N * M) {
			System.out.println(0);
			return;
		}
		
		// 모든 토마토가 익는데 몇일이 걸리는지를 나타낸다.
		int result = 0;
		
		// 기본적으로 que가 빌때까지 하는데, 초기값들은 입력받을 때 넣어놓았다.
		// 그냥 쭉 돌리는 것이 아니라 해당 단계의 que.size()만큼 돌려서 하루를 표시한다.
		while(!que.isEmpty()) {
			int size = que.size();
			
			for(int i = 0; i < size; i++) {
				int[] cur = que.poll();
				for(int j = 0; j < 4; j++) {
					int cx = cur[0] + dx[j];
					int cy = cur[1] + dy[j];
					
					if(cx >= 0 && cy >= 0 && cx < N && cy < M) {
						if(box[cx][cy] == 0) {
							box[cx][cy] = 1;
							que.add(new int[] {cx, cy});
						}
					}
				}
			}
			
			result++;
		}
		
		// 모든 칸이 비어있거나 익은 토마토만 있는지 확인한다.
		boolean check = true;
		Loop: for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(!(box[i][j] == 1 || box[i][j] == -1)) {
					check = false;
					break Loop;
				}
			}
		}
		
		// 만일 아니라면 -1 출력.
		if(!check) System.out.println(-1);
		// 맞다면 세어왔던 result를 출력한다.
		// 마지막에 다른 토마토를 익게 만드는 날이 아닌 그저 확인하는 날이 하루 존재함.
		// 그래서 result에서 1을 빼줌.
		else System.out.println(result-1);
	}

}