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

 

www.acmicpc.net/problem/7569

7569번: 토마토

 

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, h, stor[][][], d_max, r_cnt;  // day_max, to be ripe cnt
	static int dx[] = { 1, 0, 0, -1, 0, 0 };
	static int dy[] = { 0, 1, 0, 0, -1, 0 };
	static int dz[] = { 0, 0, 1, 0, 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, z, d;  // day
		public Box( int x, int y, int z, int d ) {
			this.x = x;
			this.y = y;
			this.z = z;
			this.d = d;
		}
	}
	
	public static void cntDay_BFS() {
		while( !q.isEmpty() ) {
			Box b = q.remove();
			int d_n = b.d + 1;
			for( int u = 0; u < 6; u++ ) {  // top,bottom,left,right
	            int x_n = b.x + dx[u];  // next x
	            int y_n = b.y + dy[u];  // next y
	            int z_n = b.z + dz[u];  // next z
	            if( (0 <= x_n && x_n < n) && (0 <= y_n && y_n < m) && (0 <= z_n && z_n < h) && stor[x_n][y_n][z_n] == t_u ) {
	            	q.add( new Box( x_n, y_n, z_n, d_n ) );
		            stor[x_n][y_n][z_n] = t_c;
		            r_cnt--;
					if( d_max < d_n ) 
						d_max = d_n;
	            }    
	        }
		}
	}
	
	public static int solve() {
		int i, j, k;
		boolean ripeAll = true;
		for( k = 0; k < h; k++ ) {
			for( i = 0; i < n; i++ ) {
				for( j = 0; j < m; j++ ) {
					if( stor[i][j][k] == 0 ) {
						ripeAll = false;
						r_cnt++;
					}
					if( stor[i][j][k] == 1 )
						q.add( new Box( i, j, k, 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() );
		h = Integer.parseInt( st.nextToken() );
		stor = new int[n][m][h];
		for( int k = 0; k < h; k++ ) {
			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][k] = t;
				}
			}
		}
		
		System.out.println( solve() );
		
	}
}