[백준 7569번] 토마토 (java)

사용한 방법 : BFS

 

어려웠던 점 :

하루가 지나면 익은 토마토 주변(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)의 익지 않은 토마토가 익게 되는데

문제는 "익은 토마토 주변의 익지 않은 토마토가 익어가는 행위는 하루 사이에 동시다발적으로 진행"된다는 점이었다.

처음에는 큐에서 poll할 때마다 하루가 지나는 것으로 카운트하였는데

그러면 예를 들어 처음에 5개의 익은 토마토가 있는 경우, 하루밖에 안지났는데 카운트가 5가 되어버린다.

 

해결 :

어떠한 익은 토마토가 n번째 날에 익었다면 그 주변의 익지 않은 토마토는 n+1번째 날에 익은 것이므로 

큐에 새로운 익지 않은 토마토가 있는 위치를 넣어줄 때마다 +1을 해주었다.

 

package num7569;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	private static boolean[][][] isvisited;
	private static int res;
	private static int M, N, H;
	private static Queue<Pos> q = new LinkedList<>();
	private static int[][][] graph;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] str = br.readLine().split(" ");
		M = Integer.parseInt(str[0]);
		N = Integer.parseInt(str[1]);
		H = Integer.parseInt(str[2]);

		graph = new int[H][N][M];
		isvisited = new boolean[H][N][M];

		for (int h = 0; h < H; h++) {
			for (int n = 0; n < N; n++) {
				String[] s = br.readLine().split(" ");
				for (int m = 0; m < M; m++) {
					graph[h][n][m] = Integer.parseInt(s[m]);
					if (graph[h][n][m] == 1)
						q.add(new Pos(n, m, h, 0));
				}
			}
		}
		bfs();
		
		for (int h = 0; h < H; h++) {
			for (int n = 0; n < N; n++) {
				for (int m = 0; m < M; m++) {

					if (graph[h][n][m] == 0)
						res = -1;
				}
			}
		}
		bw.write(res + "\n");
		bw.flush();

	}

	public static void bfs() {

		int[] n = { 1, -1, 0, 0, 0, 0 };
		int[] m = { 0, 0, 1, -1, 0, 0 };
		int[] h = { 0, 0, 0, 0, 1, -1 };

		while (!q.isEmpty()) {

			Pos p = q.poll();
			res = Math.max(res, p.count);

			for (int i = 0; i < 6; i++) {
				int new_n = p.n + n[i];
				int new_m = p.m + m[i];
				int new_h = p.h + h[i];

				if (0 <= new_h && new_h < H && 0 <= new_n && new_n < N && 0 <= new_m && new_m < M) {
					if (graph[new_h][new_n][new_m] == 0 && !isvisited[new_h][new_n][new_m]) {
						q.add(new Pos(new_n, new_m, new_h, p.count + 1));
						isvisited[new_h][new_n][new_m] = true;
						graph[new_h][new_n][new_m] = 1;
					}
				}

			}
		}

	}
}

class Pos {
	int m, n, h;
	int count;

	public Pos(int n, int m, int h, int count) {
		this.m = m;
		this.n = n;
		this.h = h;
		this.count = count;
	}

}