[백준/Java] 7569 - 토마토

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

문제

---

풀이

3중 배열에서 BFS를 활용하는 문제이다

익은 토마토는 하루가 지나면 상하좌우앞뒤의 익지 않은 토마토를 익게한다

이전까지는 네 방향을 확인했는데 3중 배열이니 여섯 방향을 확인해야 한다

 

익은 토마토는 첫날부터 동시에 주변 토마토를 익게한다

따라서 BFS를 시작하기 전에, 처음에 익어있던 모든 토마토의 위치를 큐에 넣고 시작해야 한다

 

토마토가 며칠째에 익었는지 기록하기 위해 따로 3차원 배열을 만들고 -1 로 초기화 해두면 방문 여부와 날짜 계산을 동시에 할 수 있다

 

자세한 것은 코드를 보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, M, H;
	static int[][][] arr;
	static int[][][] days;

	static int[] dx = {-1, 1, 0, 0, 0, 0}; // 상하
	static int[] dy = {0, 0, -1, 1, 0, 0}; // 좌우
	static int[] dh = {0, 0, 0, 0, -1, 1}; // 앞뒤

	static Queue<int[]> queue = new LinkedList<>();

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

		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로
		H = Integer.parseInt(st.nextToken()); // 높이
		arr = new int[H][N][M]; // 토마토 배열
		days = new int[H][N][M]; // 최대 며칠이 걸렸는지 확인하는 배열

		// days 배열을 -1로 초기화하면 방문 여부도 같이 확인할 수 있다
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < M; k++) {
					days[i][j][k] = -1;
				}
			}
		}

		// 토마토 배열 입력
		boolean state = false;
		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++) {
					arr[i][j][k] = Integer.parseInt(st.nextToken());
					// 입력이 1이면
					if (arr[i][j][k] == 1) {
						// 큐에 좌표를 넣어준다
						queue.add(new int[]{i, j, k});
						// days 배열 값을 0으로 한다 (방문 처리)
						days[i][j][k] = 0;
					} else if (arr[i][j][k] == 0) {
						state = true; // 익지 않은 과일이 있으면 state를 true
					}
				}
			}
		}

		// state가 true일 때만 bfs를 호출한다
		if(state) bfs();

		// bfs 탐색 후 토마토가 모두 익었는지 확인하는 변수
		boolean check = true;
		for (int[][] ints : arr) {
			for (int[] anInt : ints) {
				for (int i : anInt) {
					// 0이 하나라도 남아있으면
					if (i == 0) {
						check = false; // check 변수를 false로
					}
				}
			}
		}
		// 다 익었다면
		if (check) {
			// days 배열에서 최댓값을 찾아 출력한다
			int max = 0;
			for (int[][] day : days) {
				for (int[] ints : day) {
					for (int i : ints) {
						max = Math.max(max, i);
					}
				}
			}
			System.out.println(max);
		} else {
			// 익지 않았다면 -1을 출력
			System.out.println(-1);
		}
		br.close();
	}

	static void bfs() {
		// 큐가 빌 때까지
		while(!queue.isEmpty()) {
			// 큐에서 좌표 하나를 뺀다
			int[] coord = queue.poll();
			int h = coord[0];
			int x = coord[1];
			int y = coord[2];
			for (int i = 0; i < 6; i++) {
				// 상하좌우앞뒤 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				int nh = h + dh[i];

				// 해당 죄표가 배열 범위 안에 있고
				if (nx >= 0 && nx < N && ny >= 0 && ny < M && nh >= 0 && nh < H) {
					// 방문하지 않았고 익지 않은 토마토라면
					if (days[nh][nx][ny] == -1 && arr[nh][nx][ny] == 0) {
						queue.add(new int[]{nh, nx, ny}); // 큐에 넣어줌
						days[nh][nx][ny] = days[h][x][y] + 1; // days 배열에 며칠이 지났는지 기록
						arr[nh][nx][ny] = 1; // 익음 상태로 바꿔준다
					}
				}
			}
		}
	}
}

결과