BOJ_G5_7569

📁 [G5_7569] 토마토

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

public class Main {

	static class tomato {
		int x;
		int y;
		int z;

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

	static int M, N, H, cnt;
	static int[][][] box;
	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<tomato> queue;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// **** input start ****
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		box = new int[H][N][M];

		queue = new LinkedList<tomato>();

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int z = 0; z < M; z++) {
					box[i][j][z] = Integer.parseInt(st.nextToken());
					// 익은 토마토라면 queue 에 삽입
					if (box[i][j][z] == 1)
						queue.add(new tomato(z, j, i));
				}
			}
		}
		// **** input end ****

		System.out.println(BFS());

	} // main end

	public static int BFS() {
		// 큐가 빌때까지
		while(!queue.isEmpty()) {
			tomato to = queue.poll();

			int x = to.x;
			int y = to.y;
			int z = to.z;

			int nx,ny,nz;
			for(int i=0; i<6; i++) {
				nx = x + dx[i];
				ny = y + dy[i];
				nz = z + dz[i];

				// 범위 안에서 체크
				if(nx>=0 && ny>=0 && nz>=0 && nx<M && ny<N && nz<H) {
					// 토마토가 안익었으면
					if(box[nz][ny][nx]==0) {
						// 토마토 익혀서 추가
						queue.add(new tomato(nx, ny, nz));

						// 익은 날 + 1
						box[nz][ny][nx] = box[z][y][x] + 1;
					}
				}
			}
		}
			// 최대 날짜
			int res = Integer.MIN_VALUE;

			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) return -1;

						// 좌표에는 날짜들이 저장되어 있다.
						res = Math.max(res, box[i][j][k]);
					}
				}
			}

			// 돌기전에 이미 다 익은 토마토만 있는 경우
			if(res == 1) return 0;

			// 최대날짜에서 1빼주기
			else return res-1;
		}
} // class end

🤔 나의 생각

처음에 완탐으로 풀었으나.. 시간초과로 실패 .. ㅎ
그래서 찾아본 결과 queue + bfs 를 활용하는 것을 알 수 있었다.
내가 여기서 캐치하지 못한 것은 시간을 체크하는 방법이다..
찾은 방법에서는 시간체크를 box에 +1 씩 해가면서 나중에 전체 좌표를 돌면서 가장 큰 좌표값(시간)을 가져오는 것이다.
이 방법을 아예 생각하지 못했는데 .. 휴우 그리고 queue 쓰는 것도 생각하지 못했따..
슬프군
방법은 다음과 같다.

• queue에 익은 토마토 저장
• bfs로 6방향 탐색을 통해 토마토가 안익었으면 익히고 그 자리에 그전 box 값 + 1 해서 시간 체크
  • 결국 box에 저장되는 값은 시간 값
• queue가 빌 때 까지 돌아주고 다 돌고 나서 결과값 출력
  • 안익은 토마토가 있으면 -1
  • 돌기전에 이미 토마토가 다 익었다면 0
  • 이상이 없다면 최대값에서 -1 해주기 ( 이미 1들이 저장되어 있었기 때문에 )