[백준 7569 / 토마토 / JAVA / BFS]

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

7569번: 토마토

 

문제 접근

처음 풀어보는 3차원 문제다.

 

맵을 만들면서 안익은 토마토의 갯수를 세고 익은 토마토가 있으면 큐에 저장한다.

이후 현재 저장된 익은 토마토들의 주변만 탐색 후 안익은 토마토를 익은 토마토로 변경시켜주고 이 과정을 거치면 하루를 증가시켜준다.

while문의 조건에 따라 안익은 토마토가 더 이상 없거나 탐색할 익은 토마토가 없을 경우 반복문을 빠져나가고 

그 때 안익은 토마토의 갯수에 따라 결과를 출력한다.

 

++ 3차원으로의 사고 확장이 유연하지 못했다.

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

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

public class Main {
	static int[] dz = { 0, 0, 0, 0, 1, -1 };
	static int[] dx = { 1, -1, 0, 0, 0, 0 };
	static int[] dy = { 0, 0, 1, -1, 0, 0 };
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken()); // 가로
		int N = Integer.parseInt(st.nextToken()); // 세로
		int H = Integer.parseInt(st.nextToken()); // 높이
		
		int[][][] tomatoBox = new int[H][N][M];
		Queue<Pos> q = new LinkedList<>();
		int greenTomato = 0;
		int day = 0;
		
		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++) {
					tomatoBox[i][j][k] = Integer.parseInt(st.nextToken());
					
					// 안익은 토마토 카운팅
					if(tomatoBox[i][j][k] == 0) greenTomato++;
					
					// 익은 토마토 저장
					else if(tomatoBox[i][j][k] == 1) q.add(new Pos(i, j, k));
				}
			}
		}
				
		// 안익은 토마토가 남아있으면서 큐에도 값이 있다면,
		// 탐색할 익은 토마토가 더 이상 없거나 모든 토마토가 익으면 반복문을 탈출하게 됨
		while(greenTomato > 0 && !q.isEmpty()) {
			
			int qs = q.size(); // 딱 현재 시점에 저장해놓은 익은 토마토 주변만 탐색
			while(qs > 0) {
				qs--;
				Pos p = q.poll();
				
				int z = p.z;
				int x = p.x;
				int y = p.y;
				
				for(int i=0; i<6; i++) {
					int plusZ = z + dz[i];
					int plusX = x + dx[i];
					int plusY = y + dy[i];
					
					if(plusZ < 0 || plusZ >= H || plusX < 0 || plusX >= N || plusY < 0 || plusY >= M) continue;
					
					// 안익은 토마토가 아니라면 → 익은 토마토거나 벽이라면
					else if(tomatoBox[plusZ][plusX][plusY] !=0 ) continue;
					
					// 안익은 토마토를 익은 토마토로 변경 후 해당 좌표 저장
					greenTomato--;
					tomatoBox[plusZ][plusX][plusY] = 1;
					q.add(new Pos(plusZ, plusX, plusY));
					
				}
			}
			day++;		
		}
		
		// 모든 토마토를 익혀버렸을 경우
		if(greenTomato == 0) System.out.println(day);
		// 더 이상 익은 토마토 주변에 안익은 토마토가 없는데도 안익은 토마토가 남아있을 경우
		else System.out.println(-1);
   }
}