[백준(Baekjoon)][자바(java)] 7576 : 토마토 / DFS와 BFS

 

www.acmicpc.net/problem/7576

7576번: 토마토

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
    static Deque<Box> q = new ArrayDeque<>();
	static int m, n, stor[][], d_max, r_cnt;  // day_max, to be ripe cnt
	static int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
	static final int t_u = 0, t_r = 1, t_c = 2;  // e = -1;
	// tomato_unripe, tomato_ripe, tomato_cnted_ripe  //, empty
	
	static class Box {  // a box of the storage
		int x, y, d;  // day
		public Box( int x, int y, int d ) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	
	public static void cntDay_BFS() {
		while( !q.isEmpty() ) {
			Box b = q.remove();
			for( int u = 0; u < 4; u++ ) {  // top,bottom,left,right
	            int x_n = b.x + dx[u];  // next x
	            int y_n = b.y + dy[u];  // next y
	            int d_n = b.d + 1;
	            if( 0 <= x_n && x_n < n && 0 <= y_n && y_n < m && stor[x_n][y_n] == t_u ) {
	            	q.add( new Box( x_n, y_n, d_n ) );
		            stor[x_n][y_n] = t_c;
		           	r_cnt--;
	            	if( d_max < d_n )  
                    	d_max = d_n;
	            }
	        }
		}
	}
	
	public static int solve() {
		int i, j;
		boolean ripeAll = true;
		for( i = 0; i < n; i++ ) {
			for( j = 0; j < m; j++ ) {
				if( stor[i][j] == 0 ) {
					ripeAll = false;
					r_cnt++;
				}
				if( stor[i][j] == 1 )
					q.add( new Box( i, j, 0 ) );
			}
		}
		if( ripeAll )
			return 0;				

		cntDay_BFS();
		
		if( r_cnt == 0 )
			return d_max;
		return -1;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		m = Integer.parseInt( st.nextToken() );
		n = Integer.parseInt( st.nextToken() );
		stor = new int[n][m];
		for( int i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j = 0; j < m; j++ ) {
				int t = Integer.parseInt( st.nextToken() );
				stor[i][j] = t;
			}
		}
		
		System.out.println( solve() );	
		
	}
}