[백준] 7576 : 토마토 -JAVA - 사좋배 공유

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	//시계방향으로 돌아가기
	static int dx[] = {1,0,-1,0};
	static int dy[] = {0,1,0,-1};
	static int arr[][];
	static int M,N;
	static Queue q;

	private static void BFS() {
		while(!q.isEmpty()) {
			tomato t1= q.poll();
			int x = t1.x;
			int y = t1.y;
			arr[x][y]=t1.count;
			
			for(int i=0;i<4;i++) {
				int rx = x + dx[i];
				int ry = y + dy[i];
				if(rx<0||ry<0||rx>=N||ry>=M||arr[rx][ry]==1) {
					continue;
				}
				if(arr[rx][ry]>arr[x][y]+1||arr[rx][ry]==0) {
					arr[rx][ry] =arr[x][y]+1;
					tomato t= new tomato(rx,ry,arr[x][y]+1);
					q.add(t);
				}

			}
//			for(int i=0;i<N;i++) {
//				for(int j=0;j<M;j++) {
//					System.out.print(arr[i][j]);
//				}
//				System.out.println();
//			}
//			System.out.println();
		}
	}
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		//입력받기
		M = sc.nextInt();
		N = sc.nextInt();
		arr= new int [N][M];
		int sum =0;
		int max= Integer.MIN_VALUE;
		q= new LinkedList();
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		
		
		//채울때부터 다 1이면 그냥 0출력하고 나오기
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				sum = sum+arr[i][j];
			}
		}
		if(sum==N*M) {
			System.out.println("0");
			return;
		}
		
		
		
		//실질적인 로직.
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(arr[i][j]==1) {
					tomato t= new tomato(i,j,1);
					q.add(t);
				}
			}
		}
		BFS();
		
		//출력
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(arr[i][j]>max) {
					max=arr[i][j];
				}
				//익지않은 토마토가 있으면 -1 출력
				if(arr[i][j]==0) {
					System.out.println("-1");
					return;
				}
			}
		}
		System.out.println(max-1);
	}

	
	//토마토 클래스
	
	static class tomato{
		public int x;
		public int y;
		public int count;
		tomato(int x, int y,int count){
			this.x = x;
			this.y= y;
			this.count=count;
		}
	}

}