7569 토마토

문제 이해

3차원 배열이 존재한다.
1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어 있지 않은 칸이다.

이 때, 익은 토마토는 하루에 한 번씩 익지 않은 토마토를 익게 한다.
익게 되는 토마토는 위쪽, 아래쪽, 그리고 같은 층의 상하좌우에 존재하는 익지 않은 토마토이다.
토마토가 들어있지 않은 칸은 토마토가 없으므로 토마토가 익을 수도, 익힐 수도 없다.

이 때 모든 토마토가 익을 때까지 걸리는 최소 시간을 출력하는 문제이다.


문제 풀이

처음에 익지 않은 토마토 개수를 A라고 가정하자.
이 때 토마토가 한 개 익을 때마다 A를 1씩 감소시키면, A = 0이 되는 순간이 모든 토마토가 익은 순간이 될 것이다.
재귀함수를 사용하면 A = 0이 되는 순간을 처리하기 어려울 것이라는 생각을 하여 BFS를 통해 문제를 해결하기로 하였다.

먼저 익은 토마토의 위치를 저장해 놓을 것이다.

이후, 일자에 따라 토마토의 상하좌우, 위 아래에 존재하는 익지 않은 토마토를 익힐 것이다. 마지막으로, 익은 토마토가 인접한 모든 토마토를 익혔으면 다음부터는 이 토마토는 더 이상 익힐 토마토가 없으므로 더 이상 Search 하지 않아도 된다.
따라서, visit을 true로 만들어준다.

마지막으로 A = 0이 되기 직전에 내가 Search 했던 좌표의 토마토가 익을 때 까지 걸린 시간이 정답이 될 것이다.


코드

import java.io.*;
import java.util.*;

class Tomato{
	int x;
	int y;
	int z;
	int day;
	
	public Tomato(int x,int y,int z,int day) {
		this.x = x;
		this.y = y;
		this.z = z;
		this.day = day;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M, H;
	static int[][][] arr;
	static int need_fill = 0;
	static Queue<Tomato> sub = new LinkedList<>();
	
	static Integer bfs() {
		int day = -1;
		need_fill+=sub.size();
		while(!sub.isEmpty()) {
			if(need_fill==0) return day; 
             // 익힐 토마토가 없으므로 모든 토마토가 익었다.
             // 따라서 직전에 검사한 토마토가 익을 때까지의 시간이 저장된 
             // day를 반환시킨다.
			
			Tomato tmp = sub.poll();
			
			if(tmp.x<0 || tmp.y<0 || tmp.z<0 || tmp.x>=N || tmp.y>=M 
                                                 || tmp.z>=H) continue;
			if(arr[tmp.x][tmp.y][tmp.z]!=0) continue;
            // 해당 위치는 이미 익은 토마토이거나, 토마토가 없는 곳이다.
            // 따라서 생략한다.
			
            arr[tmp.x][tmp.y][tmp.z] = 1;
			need_fill--;
            // 처음으로 익지 않은 토마토가 익었다. 
            // 따라서, 익지 않은 토마토 개수를 1개 빼준다.
            
			day = tmp.day;
            // 우리는 need_fill = 0이 되기 "직전"에 검사하는 위치의
            // 토마토가 익을 때까지 걸린 시간이 필요하다
            // 따라서, day 공간에 계속해서 현재 검사하고 있는 익지 않은
            // 토마토가 익을 때까지 걸린 시간을 저장할 필요가 있다.
			
			sub.add(new Tomato(tmp.x+1,tmp.y,tmp.z,tmp.day+1));
			sub.add(new Tomato(tmp.x-1,tmp.y,tmp.z,tmp.day+1));
			
			sub.add(new Tomato(tmp.x,tmp.y+1,tmp.z,tmp.day+1));
			sub.add(new Tomato(tmp.x,tmp.y-1,tmp.z,tmp.day+1));
			
			sub.add(new Tomato(tmp.x,tmp.y,tmp.z+1,tmp.day+1));
			sub.add(new Tomato(tmp.x,tmp.y,tmp.z-1,tmp.day+1));
		}
	
		return -1;
        // 이곳에 도착했다는 것은 need_fill = 0인 Case가 없었다는 의미이다.
        // 즉, 모든 토마토가 익지 않았으므로 -1을 반환한다.
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();
		
		M = sc.nextInt();
		N = sc.nextInt();
		H = sc.nextInt();
		
		arr = new int[N][M][H];
		for(int k =0;k<H;k++) {
			for(int i = 0;i<N;i++) {
				for(int j =0;j<M;j++) {
					int tmp = sc.nextInt();
					
					switch(tmp) {
					case 0:
						need_fill++;
						break;
					case 1:
						sub.add(new Tomato(i,j,k,0));
						tmp = 0;
						break;
					}
					
					arr[i][j][k] = tmp;
				}
			}
		}
		
		System.out.println(bfs());
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

좋은 웹페이지 즐겨찾기