[백준] 7576 토마토 - JAVA

1. 문제 유형 : BFS

2. 시간 복잡도 : O(MN)

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

public class Main {

	static int[] dy = { -1, 0, 1, 0 };
	static int[] dx = { 0, 1, 0, -1 };
	static int N, M, box[][], answer = 0;
	static boolean[][] visited;

	static class Tomato {
		int x, y, days;

		public Tomato(int x, int y, int days) {
			super();
			this.x = x;
			this.y = y;
			this.days = days;
		}

		@Override
		public String toString() {
			return "Tomato [x=" + x + ", y=" + y + ", days=" + days + "]";
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		box = new int[N][M];
		visited = new boolean[N][M];
		int notCnt = 0;
		Queue<Tomato> q = new LinkedList<Tomato>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				int temp = Integer.parseInt(st.nextToken());
				box[i][j] = temp;
				if(temp == 1) q.offer(new Tomato(j, i, 1));
				if(temp == 0) notCnt++;
			}
		}
		if(notCnt == 0) {
			System.out.println(0);
			return;
		}
		while(!q.isEmpty()) {
			Tomato current = q.poll();
			for (int i = 0; i < 4; i++) {
				int nextY = current.y + dy[i];
				int nextX = current.x + dx[i];
				if(nextX >= 0 && nextX < M && nextY >= 0 && nextY < N && box[nextY][nextX] == 0) {
					box[nextY][nextX] = 1; 	// 토마토 익음
					answer = Math.max(answer, current.days);
					q.offer(new Tomato(nextX, nextY, current.days+1));
				}
			}
		}
		
		// 만약에 더이상 진행할 토마토가 없는데, 0이 남아있다면 -1
		// 0이 남아있지 않다면 0
		for (int i = 0; i <	N; i++) {
			for (int j = 0; j < M; j++) {
				if(box[i][j] == 0) answer = -1;
			}
		}
		System.out.println(answer);
	}
}