백준 7569 토마토(Gold 5)

정답코드

import java.util.*;

class Location {
	int z;
	int y;
	int x;

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//3차원을 탐색하기 위해서 좌표 2개 더 추가함
        int[] rz = { 0, 0, 0, 0, -1, 1 };
		int[] ry = { 0, 0, -1, 1, 0, 0 };
		int[] rx = { -1, 1, 0, 0, 0, 0 };

		int m = sc.nextInt();
		int n = sc.nextInt();
		int h = sc.nextInt();

		int[][][] tomato = new int[h][n][m];
		Deque<Location> redTomato = new ArrayDeque<>();
		
		int greenTomato = 0, days = 0;

		for (int i = 0; i < h; i++)
			for (int j = 0; j < n; j++)
				for (int k = 0; k < m; k++) {
					tomato[i][j][k] = sc.nextInt();
					if (tomato[i][j][k] == 0)
						greenTomato++;
					else if (tomato[i][j][k] == 1)
						redTomato.add(new Location(i, j, k));
				}
		//안 익은 토마토가 0보다 크고 익은 토마토 큐가 빌 때까지 반복
		while (greenTomato > 0 && !redTomato.isEmpty()) {
			int size = redTomato.size();
			for(int i = 0; i < size; i++){
				Location l = redTomato.remove();
				int z = l.z;
				int y = l.y;
				int x = l.x;

				for (int j = 0; j < 6; j++) {
					int nz = z + rz[j];
					int ny = y + ry[j];
					int nx = x + rx[j];
					
                    //범위를 벗어나는 경우 continue
					if (nz < 0 || ny < 0 || nx < 0 || nz >= h || ny >= n || nx >= m)
						continue;
                    //다음 토마토가 안 익은 토마토가 아니면 continue
					else if (tomato[nz][ny][nx] != 0)
						continue;
					
                    //안 익은 토마토 수를 줄이고
					greenTomato--;
                    //익은 토마토로 바꾼다
					tomato[nz][ny][nx] = 1;
                    //익은 토마토 queue에 넣어준다
					redTomato.add(new Location(nz, ny, nx));
				}
			}
			days++;
		}
        
		System.out.println(greenTomato == 0 ? days : -1);
	}
}

전략

• 3차원 BFS를 돌려줘야 한다 -> 사실상 2차원인데 이동값만 추가 됨

• 익은 토마토들을 처리할 Qeueu가 필요함 BFS 최단거리 체크

• 안 익은 토마토가 더이상 남지 않았거나 현재 단계에서 익은 토마토를 확산시켰는데 다음 스탭에 익은 토마토가 들어오지 않는 경우 break해준다

• 익은 토마토를 모두 Queue에 넣어서 각자의 위치에서 확산시켜줘야 한다