[JAVA 자바] 백준 7569번 : 토마토

▶ 문제

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

7569번: 토마토

▶ 설명

단계별 문제풀기에서 바로 이전 문제인 토마토에서 변형된 문제이다.

이전 문제에서의 토마토 상자                                     현 문제에서의 토마토 상자

왼쪽은 그림은 2차원 배열로 토마토 상태를 입력받아 아래, 위, 좌, 우를 탐색하여 방문했던 반면, 

오른쪽 그림은 3차원 배열로 토마토 상태를  입력받은 다음 가로세로 방향으로 아래, 위, 좌, 우, 높이 방향으로 위,아래를 탐색해야 한다. 탐색할 곳의 방향의 수가 증가하여  4번 탐색에서 6번 탐색으로 2번의 탐색을 추가한 셈이다.

그림으로 살펴보면 다음과 같다.

2차원 배열에서 탐색 가능한 인덱스

3차원 배열에서 탐색 가능한 인덱스

이 문제는 3차원 배열로 풀어야 하므로 두번째 그림을 참고하여 방문할 인덱스를 구성하면 된다.

나머지 풀이는 이전 문제인 토마토와 같아서 생략한다. 7576 토마토 풀이

 

 

 

 

▶ 문제 풀이

🌱 풀이.  

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

public class Main {
	static int[][][] box;
	static ArrayList<Tomato3d> list = new ArrayList<>();
	static int h, n, m;

	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()); // 높이

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

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int k = 0; k < m; k++) {
					box[i][j][k] = Integer.parseInt(st.nextToken());                
					if (box[i][j][k] == 1) {
						list.add(new Tomato3d(i, j, k));
					}
				}
			}
		}


		int result = bfs() - 1;
		LOOP: for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (box[i][j][k] == 0) {
						result = -1;
						break LOOP;
					}
				}
			}
		}
		System.out.println(result);


	}

	private static int bfs() {
		int z = 0, x = 0, y = 0;
		int[] az = { -1, 0, 0, 0, 0, 1 };
		int[] ay = { 0, 0, 0, -1, 1, 0 };
		int[] ax = { 0, -1, 1, 0, 0, 0, };

		Queue<Tomato3d> q = new LinkedList<>();
		for (int i = 0; i < list.size(); i++) {
			q.offer(list.get(i));
		}

		while (!q.isEmpty()) {
			Tomato3d tomato = q.poll();
			z = tomato.getZ();
			x = tomato.getX();
			y = tomato.getY();

			for (int i = 0; i < 6; i++) {
				int nz = z + az[i];
				int nx = x + ax[i];
				int ny = y + ay[i];

				if (nx >= n || ny >= m || nz >= h || nx < 0 || ny < 0 || nz < 0) {
					continue;
				}
				if (box[nz][nx][ny] == 0) {
					q.offer(new Tomato3d(nz, nx, ny));

					box[nz][nx][ny] = box[z][x][y] + 1;

				}

			}
		}

		return box[z][x][y];
	}

}

class Tomato3d {
	private int z;
	private int x;
	private int y;

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

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getZ() {
		return z;
	}
}

 

 

 

▶ Log

이 문제는 시간초과가 날 가능성이 있다.

조건을 타이트하게 짜야 Queue에 불필요한 데이터가 들어가지 않을 수 있고

그러면 시간초과라는 결과를 피할 수 있을 것이다.