[Java] 백준 7569 : 토마토

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

7569번: 토마토

---

 

이 문제는 7576번 토마토문제와 같은 방식으로 풀면 되는 문제이다. 

이전 문제와 차이점은 2차원에서 3차원으로 늘어났다는 것이다. 

어렵지 않다. 

 

첫 번째로 할 일은 3차원의 배열을 입력받는 것이다. 

두 번째로는 입력받은 토마토 배열을 가지고 토마토가 익어 있을 경우를 판단하는 것이다. 

보통 너비우선 탐색을 진행하면 차근차근 처음부터 탐색해 가면서 큐를 사용하여 탐색을 하지만 이 문제의 경우에는 익은 토마토에서부터 동시에 시작이 되어야 하므로 순차적으로 앞에 있던 토마토부터 시작을 하게 되면 옳지 않은 답은 얻게 된다.  그래서 미리 큐에 익어 있는 토마토의 좌표를 넣어놔야 한다. 

for (int k = 0; k < inputZ; k++) {
			for (int i = 0; i < inputX; i++) {
				for (int j = 0; j < inputY; j++) {
					if (arr[k][i][j] == 1) {
						qu.add(new point(k, i, j));

					}
				}
			}
		}

삼차원이라 for문도 3중 구조이다. 

 

 

세번째로는 이 큐를 가지고 너비우선 탐색을 진행한다. 

영향을 주는 토마토의 범위는 익은 토마토를 기준으로 동일한 상자에서 상하좌우, 윗상자와 아랫상자에서 바로 익은 토마토와 접해있는 토마토로 총 6개의 토마토를 검사해야 한다. 

그 좌표는 이렇다.

static int[] dx = { 0, 0, -1, 1, 0, 0 };
static int[] dy = { 1, -1, 0, 0, 0, 0 };
static int[] dz = { 0, 0, 0, 0, -1, 1 };

이 좌표를 가지고 순서대로 검사를 하면 된다. 

 

반응형

 

해당 좌표에 0보다 크거나 같고, 입력받은 xyz범위보다 작으면, 그리고 익어 있지 않은 토마토라면

큐에 집어넣고 해당 토마토가 익은 날짜를 알기 위해 기준 토마토의 날짜+1의 값을 넣어준다. 

for (int i = 0; i < 6; i++) {
				int nx = tx + dx[i];
				int ny = ty + dy[i];
				int nz = tz + dz[i];

				if (nx >= 0 && ny >= 0 && nz >= 0 && nx < inputX && ny < inputY && nz < inputZ) {
					if (arr[nz][nx][ny] == 0) {
						qu.add(new point(nz, nx, ny));
						arr[nz][nx][ny] = arr[tz][tx][ty] + 1;
					}
				}

			}

 

 

마지막으로는 탐색을 마친 토마토 상자 배열을 가지고 토마토가 모두 익었는지 아닌지 , 익었다면 며칠이 걸렸는지 출력하는 일만 남았다. 

순차적으로 0,0,0부터 시작해서 끝까지 탐색을 해가면서 0이 있다면 -1을 모든 날이 1이라면 0을, 영향을 받아 모두 익은 토마토가 되었다면 얼마나 걸렸는지 출력해 주면 된다. 

주의해야 할 것은 애초에 익어 있던 토마토가 1로 시작했기 때문에 -1을 해줘야한다. 

for (int k = 0; k < inputZ; k++) {
			for (int i = 0; i < inputX; i++) {
				for (int j = 0; j < inputY; j++) {
					if (arr[k][i][j] == 0) {
						System.out.println(-1);
						return;
					}
					days = Math.max(days, arr[k][i][j]);
				}
			}
		}

		if (days == 1)
			System.out.println(0);
		else {
			System.out.println(days - 1);
		}

 

 

---

최종 코드

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

public class Main {

	static int inputX, inputY, inputZ;
	static int[][][] arr;
	static int[] dx = { 0, 0, -1, 1, 0, 0 }; // 상,하,좌,우, 앞,뒤
	static int[] dy = { 1, -1, 0, 0, 0, 0 };
	static int[] dz = { 0, 0, 0, 0, -1, 1 };
	static Queue<point> qu = new LinkedList<>();

	static class point {
		int x, y, z;

		point(int z, int x, int y) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}// class point

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		inputY = Integer.parseInt(str[0]); // 가로
		inputX = Integer.parseInt(str[1]); // 세로
		inputZ = Integer.parseInt(str[2]); // 상자 수

		arr = new int[inputZ][inputX][inputY];

		for (int k = 0; k < inputZ; k++) {
			for (int i = 0; i < inputX; i++) {
				String[] str1 = br.readLine().split(" ");
				for (int j = 0; j < inputY; j++) {
					arr[k][i][j] = Integer.parseInt(str1[j]);
				}
			}
		}

		for (int k = 0; k < inputZ; k++) {
			for (int i = 0; i < inputX; i++) {
				for (int j = 0; j < inputY; j++) {
					if (arr[k][i][j] == 1) {
						qu.add(new point(k, i, j));

					}
				}
			}
		}
		bfs();
		checkTomato();

	}// main()

	static void bfs() {
		while (!qu.isEmpty()) {
			point tmp = qu.poll();
			int tz = tmp.z;
			int tx = tmp.x;
			int ty = tmp.y;

			for (int i = 0; i < 6; i++) {
				int nx = tx + dx[i];
				int ny = ty + dy[i];
				int nz = tz + dz[i];

				if (nx >= 0 && ny >= 0 && nz >= 0 && nx < inputX && ny < inputY && nz < inputZ) {
					if (arr[nz][nx][ny] == 0) {
						qu.add(new point(nz, nx, ny));
						arr[nz][nx][ny] = arr[tz][tx][ty] + 1;
					}
				}

			}

		}
	}// bfs()

	static void checkTomato() {
		int days=0;
		
		for (int k = 0; k < inputZ; k++) {
			for (int i = 0; i < inputX; i++) {
				for (int j = 0; j < inputY; j++) {
					if (arr[k][i][j] == 0) {
						System.out.println(-1);
						return;
					}
					days = Math.max(days, arr[k][i][j]);
				}
			}
		}

		if (days == 1)
			System.out.println(0);
		else {
			System.out.println(days - 1);
		}

	}// checkTomato()

}// class Main