백준 7569번 : 토마토(Java)

 

7569번: 토마토

---

[풀이]

 

- BFS를 이용하여 풀었습니다.(7576번 문제와 거의 유사합니다. 차이점은 h(높이)에 대한 것이 있냐 없냐입니다.)
- 7576번 토마토 문제에는 높이(h)가 없지만, 이번에는 h가 추가되어 3차원으로 arr을 선언해야 합니다.
- 익은 토마토가 가지고 있는 토마토에 전부 영향을 줘야 하기 때문에 queue에 담긴 위치를 기반으로 모든 토마토를 익게 할 때까지 횟수를 기록해야합니다.
  - 이때, 횟수는 이전에 arr 2차원 배열에 기록된 것에 +1 함으로써 기록할 수 있습니다.
- 주어진 값에서 1(익은 토마토)인 경우 모두 큐에 담아 이 큐에 담긴 Point 값이 시작 지점이 됩니다.
- 이후, queue에서 하나씩 값을 꺼내 익지 않은 토마토(0)일 경우, 새로 queue에 담으며 queue가 빌 때까지 이 과정을 반복합니다.
- 마지막으로, 값을 전체 확인하며 아직 익지 않은 토마토가 있을 경우 -1을 반환하고 이외에 정상적으로 while문이 실행되었을 경우에는 최종 count를 반환합니다.

---

[코드]

 

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int m, n, h, answer;
	static int[][][] arr;
	static Queue<Point> queue = new LinkedList<>();
	static int[] dx = {-1, 0, 1, 0, 0, 0};
	static int[] dy = {0, 1, 0, -1, 0, 0};
	static int[] dz = {0, 0, 0, 0, 1, -1};

	static class Point {

		int x, y, z;

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

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		m = sc.nextInt();
		n = sc.nextInt();
		h = sc.nextInt();
		answer = 1;

		arr = new int[h][n][m];

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					arr[i][j][k] = sc.nextInt();
					if (arr[i][j][k] == 1) {
						queue.offer(new Point(i, j, k));
					}
				}
			}
		}

		System.out.println(solve());
	}

	public static int solve() {
		while (!queue.isEmpty()) {
			Point poll = queue.poll();
			for (int i = 0; i < 6; i++) {
				int nextX = poll.x + dx[i];
				int nextY = poll.y + dy[i];
				int nextZ = poll.z + dz[i];

				if (nextX >= 0 && nextY >= 0 && nextZ >= 0 && nextX < n && nextY < m && nextZ < h) {
					if (arr[nextZ][nextX][nextY] == 0) {
						queue.offer(new Point(nextZ, nextX, nextY));
						arr[nextZ][nextX][nextY] = arr[poll.z][poll.x][poll.y] + 1;
					}
				}
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (arr[i][j][k] == 0) {
						return -1;
					}
					answer = Math.max(answer, arr[i][j][k]);
				}
			}
		}
		if (answer == 1) {
			return 0;
		} else {
			return answer - 1;
		}
	}
}