토마토 [백준 7569][실버1][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

7569번: 토마토

3차원 토마토

BFS를 사용하여 동시에 퍼지게 구현하였고 한번 퍼지면 날짜가 증가하게 하였다.

BFS연습하기 좋은 문제.

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

public class Main {

	public static final int[] dx = { -1, 0, 1, 0 };
	public static final int[] dy = { 0, 1, 0, -1 };
	public static final int[] dh = { -1 , 1 };
	public static int[][][] map;
	public static boolean[][][] visit;
	public static Queue<int[]> q;
	public static int N, M, cnt, day, H;
	public static int unripeTomato;
	
	public static void main(String[] args) throws Exception {

		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()); // 높이
		
		map = new int[H][N][M];
		q = new LinkedList<>();
		for (int k = 0; k < H; k++) {
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[k][i][j] = Integer.parseInt(st.nextToken());
					if(map[k][i][j] == 0) unripeTomato++;
					if (map[k][i][j] == 1) { // 이미 익었다.
						q.add(new int[] { k, i, j  });
					}
				}
			}
		}

		bfs();
		if (unripeTomato == 0) {
			System.out.println(day-1);
			return;
		}else {
			System.out.println(-1);
		}
	}

	public static void bfs() {
		visit = new boolean[H][N][M];
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) { // 큐의 사이즈 만큼
				int[] arr = q.poll();

				visit[arr[0]][arr[1]][arr[2]] = true; // 방문처리

				for (int j = 0; j < 4; j++) { // 상하좌우
					int nx = arr[1] + dx[j];
					int ny = arr[2] + dy[j];

					CheckTomato(arr[0] , nx, ny);
				}
				for (int j = 0; j < 2; j++) {
					int nh = arr[0] + dh[j];
					CheckTomato(nh, arr[1], arr[2]);
				}
			}
			day++;
		}
	}

	private static void CheckTomato(int h ,int nx, int ny) {
		if (h < 0 || h>= H ||nx < 0 || nx >= N || ny < 0 || ny >= M) { // 선을 넘으면
			return;
		}
		if (map[h][nx][ny] == 0 && !visit[h][nx][ny] && map[h][nx][ny] != -1) { // 안익은 토마토 일 때
			q.add(new int[] { h, nx, ny });
			map[h][nx][ny] = 1; // 익힌다.
			unripeTomato--;
			visit[h][nx][ny] = true;
		}
	}
}