백준 7569번
https://www.acmicpc.net/problem/7569

---

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

예제 입력

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

---

예제 출력

-1

---

생각하기

저번에 풀었었던 토마토문제의 진화 버전이다.
자바 알고리즘 문제를 풀면서 3차원 배열을 사용하면 된다.

동작

		// 5, 3, 2
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 상자의 가로 칸의 수 x
		N = Integer.parseInt(st.nextToken()); // 상자의 세로 칸의 수 y
		H = Integer.parseInt(st.nextToken()); // 상자의 수 z

		boolean zero = false;
		box = new int[H][N][M];

먼저 BFS()메소드에서 사용할 수 있게 배열과 변수를 만들어준다.

2.

		boolean zero = false;
		box = new int[H][N][M];

		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				String str = br.readLine(); 
				st = new StringTokenizer(str);

				for(int k=0; k<M; k++) {
					int num = Integer.parseInt(st.nextToken());

					if(num == 0) {
						zero = true;
					}
					else if(num == 1) {
						que.offer(new Node(i, j, k));
					}

					box[i][j][k] = num;
				}
			}
		}

		if(zero == false) {
			System.out.println(0);
			return;
		}

배열을 입력값에 맞게 만들어주고 boolean으로 zero변수를 만들어줘서 0이 한번이라도 들어올 경우, true로 바꿔주고 여전히 false일 경우, 바뀔 토마토가 없다는 의미로 바로 0을 출력하고 종료한다.

static void BFS() {
		count = 0;

		while(!que.isEmpty()) {
			Node node = que.poll();

			for(int i=0; i<6; i++) {
				nowX = node.x + dirX[i];
				nowY = node.y + dirY[i];
				nowZ = node.z + dirZ[i];

				if(Range_check() && box[nowZ][nowY][nowX] == 0) {
					box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;
					que.offer(new Node(nowZ, nowY, nowX));
				}	
			}
		}
	} // End of BFS()

BFS() 메소드는 3차원 배열만을 제외한다면 일반 BFS와는 특별히 다른 점이없다.

그나마 찾는다면 상자에서 토마토가 전체 익는 날짜를 계산하기 위해서 이전의 값을 새로운 좌표값에 1을 더 해서 값을 넣어준다는 것이다.

box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;

		int max = Integer.MIN_VALUE / 16;
		for(int num[][] : box) {
			for(int num2[] : num) {						
				for(int num3 : num2) {

					if(num3 == 0) {
						System.out.println(-1);
						return;
					}

					if(max < num3) {
						max = num3;
					}
				}
			}
		}

		System.out.println(max - 1);

마지막은 배열을 전체 탐색해서 배열의 최댓값을 출력하면, 토마토가 전체 익는 날짜를 알 수 있다.

그리고 만약 0이 남아있다면 0을 출력하고 바로 종료를 하면된다.

그리고 누적합을 구했기 때문에 시작이 1이었음을 감안해서 마지막 결과값은 -1을 해줘야한다.

---

코드

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

class Node {
	int z;
	int y;
	int x;

	public Node(int z, int y, int x) {
		this.z = z;
		this.y = y;
		this.x = x;
	}
}

public class Main {
	static int box[][][];
	static int dirX[] = {0, 0, -1, 1, 0, 0}; // 상, 하, 좌, 우, 위, 아래
	static int dirY[] = {-1, 1, 0, 0, 0, 0};
	static int dirZ[] = {0, 0, 0, 0, 1, -1};
	static Queue<Node> que = new LinkedList<>();

	static int nowX, nowY, nowZ, N, M, H, count;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// 5, 3, 2
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 상자의 가로 칸의 수 x
		N = Integer.parseInt(st.nextToken()); // 상자의 세로 칸의 수 y
		H = Integer.parseInt(st.nextToken()); // 상자의 수 z

		boolean zero = false;
		box = new int[H][N][M];

		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				String str = br.readLine(); 
				st = new StringTokenizer(str);

				for(int k=0; k<M; k++) {
					int num = Integer.parseInt(st.nextToken());

					if(num == 0) {
						zero = true;
					}
					else if(num == 1) {
						que.offer(new Node(i, j, k));
					}

					box[i][j][k] = num;
				}
			}
		}

		if(zero == false) {
			System.out.println(0);
			return;
		}

		BFS();

		int max = Integer.MIN_VALUE / 16;
		for(int num[][] : box) {
			for(int num2[] : num) {						
				for(int num3 : num2) {

					if(num3 == 0) {
						System.out.println(-1);
						return;
					}

					if(max < num3) {
						max = num3;
					}
				}
			}
		}

		System.out.println(max - 1);

	} // End of main

	static void BFS() {
		count = 0;

		while(!que.isEmpty()) {
			Node node = que.poll();

			for(int i=0; i<6; i++) {
				nowX = node.x + dirX[i];
				nowY = node.y + dirY[i];
				nowZ = node.z + dirZ[i];

				if(Range_check() && box[nowZ][nowY][nowX] == 0) {
					box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;
					que.offer(new Node(nowZ, nowY, nowX));
				}	
			}
		}
	} // End of BFS()

	static boolean Range_check() {
		return (nowX < M && nowX >= 0 && nowY < N && nowY >= 0 && nowZ < H && nowZ >= 0);
	} // End of Range_check()

} // End of class