토마토 (BFS)

생각해 볼 점

1. 익은토마토(1) 의 입력값을 받을 때 미리 배열에 저장 (최적화)

2. 기존의 문제와 달리, 동시 다발적으로 퍼져나감. (초기 Q에 들어있는 값이 여러개)

3. 입력과 동시에 초기화.

4. 레벨 탐색기반으로 level이 답이 된다. 그러나 box가 모두 1이 되었을 때, Q안에 들어있는 위치는 검사할 필요가 없으므로 -1을 보정해준다.

 

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

class Main {

	static int m, n, answer;
	
	//-1 토마토 없음
	// 1 익은 토마토
	// 0 토마토
	
	int []dx = {0, 0, 1, -1};
	int []dy = {1, -1, 0, 0};
	static Queue<Position> Q;
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		m = in.nextInt();
		n = in.nextInt();
		Q = new LinkedList<>();
				
		int [][]box = new int [n+1][m+1];
		int [][]dis = new int [n+1][m+1];
		boolean flag = true;
		for (int i =1; i <= n ; ++i) {
			for (int j = 1; j <= m ; ++j) {
				box[i][j] = in.nextInt();
				if( box[i][j] == 1) {					
					Q.offer(M.new Position(i,j));
					flag = false;
				}
			}
		}
		
		if(flag) {
			System.out.println(0);
			return;
		}
		
		
		M.BFS(box, dis);
		
		for (int i =1; i <= n ; ++i) {
			for (int j = 1; j <= m ; ++j) {
				if( box[i][j] == 0 )
					answer = -1;
			}
		}
		if( answer == -1) {
			System.out.println(answer);
			return;
		}
			
		
		for ( int [] d : dis)
			  answer = Math.max(answer, Arrays.stream(d).max().getAsInt());
		
		System.out.println(answer);
	}

	private void BFS(int[][] box, int[][]dis) {
	
		int level = 0;
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for ( int idx = 0 ; idx < len ; ++idx ) {
				Position p = Q.poll();
				for ( int i = 0 ; i < 4 ; ++i) {
					int nx = p.x + dx[i];
					int ny = p.y + dy[i];
					if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && box[nx][ny] ==0) {
						
						box[nx][ny] = 1;
						dis[nx][ny] = dis[p.x][p.y] + 1;
						Q.offer(new Position(nx, ny));
					}
				}
				
			}
			level++;
		}
		/*토마토가 다 변한 다음 Q안에 남은 값을 보정*/
		//answer = level-1;
		
		//or dis의 max값 
		/*
		for (int i =1; i <= n ; ++i) {
			for (int j = 1; j <= m ; ++j) {
				System.out.print(dis[i][j] + " ");
			}
			System.out.println();
		}
		*/

		
	}

	class Position{
		int x,y;
		Position( int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}