⭐ [백준] 7569번: 토마토 (Java/자바)

 

문제

https://www.acmicpc.net/problem/7569

 

 

문제풀이

전형적인 BFS 문제이다. 익지 않은 토마토를 Queue에 담고 순차적으로 높게, 낮게, 상, 하, 좌, 우 방향으로 움직이며 탐색하면 되는 문제이다. 아래와 같은 조건을 주의해야 한다.

 

1. 토마토가 모두 익지 않을 때는 `0` 을 출력한다. (토마토가 모두 익지 않는 경우가 존재한다.)

2. 상자의 일부에는 토마토가 존재하지 않을 수 있다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {	
	public static int M, N, H, res;
	public static int[][][] map;
	
	public static int[] dx = {0, 0, 0, 0, -1, 1};
	public static int[] dy = {0, 0, -1, 1, 0, 0};
	public static int[] dh = {-1, 1, 0, 0, 0, 0};
	
	public static Queue<tomato> q = new LinkedList<>();
	
	public static class tomato {
		int x, y, h, d;
		public tomato(int h, int y, int x, int d) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.d = d;
		}
	}
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String[] param = br.readLine().split(" ");
    	M = Integer.parseInt(param[0]);
    	N = Integer.parseInt(param[1]);
    	H = Integer.parseInt(param[2]);
    	
    	map = new int[H][N][M];
    	
    	for(int i = H-1; i >= 0; i--) {
    		for(int j = 0; j < N; j++) {
    			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    			for(int k = 0; k < M; k++) {
    				map[i][j][k] = Integer.parseInt(st.nextToken());
    				if(map[i][j][k] == 1) q.add(new tomato(i, j, k, 0));
    			}
    		}
    	}
    	
    	while(!q.isEmpty()) {
    		tomato t = q.poll();
    		
    		for(int i = 0; i < 6; i++) {
    			int h = t.h + dh[i];
    			int y = t.y + dy[i];
     			int x = t.x + dx[i];
    			
    			if(h < 0 || h >= H || x < 0 || x >= M || y < 0 || y >= N || map[h][y][x] == 1 || map[h][y][x] == -1) continue;
    			
    			map[h][y][x] = 1;
    			res = Math.max(t.d+1, res);
    			q.add(new tomato(h, y, x, t.d+1));
    		}
    	}
    	
    	
    	for(int i = 0; i < H; i++) {
    		for(int j = 0; j < N; j++) {
    			for(int k = 0; k < M; k++) {
    				if(map[i][j][k] == 0) {
    					System.out.println(-1);
    					System.exit(0);
    				}
    			}
    		}
    	}
    	
    	System.out.println(res);
    }
}