[백준] 7569번 토마토

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

7569번: 토마토

---

[풀이 방법]

🔅 각 단위 별 로직

▶ 토마토가 모두 익지 못하는 상황을 판별해야함

  -> 토마토를 입력받을 때, 익지 않은 토마토(0)의 개수를 세서 변수 unripe에 저장

  -> 익게한 토마토의 개수를 세서 ripe 변수에 저장

  -> 익게한 토마토의 개수가 익지 않은 토마토의 개수보다 작을 경우 토마토가 모두 익지 못하는 상황이므로 -1출력

 

▶ 1일차에는 0일차에 익은 토마토의 주변 토마토가 익고, 2일차에는 1일차에 익은 토마토의 주변 토마토가 익고,

  3일차에는 2일차에 익은 토마토의 주변 토마토가 익고....

  -> n일차에는 n-1일차에 익은 토마토의 주변 토마토가 익음

  -> 즉, 날짜 단위로 끊어서 주변 토마토를 익게 해야함 

 

▶ Queue자료구조를 사용해서 익은 토마토를 큐에 추가하여 다음 날이 되면 빼서 주변 토마토들을 익게한다.

 

🔅 전체 로직

1. 토마토를 입력받으면서 익지않은 토마토(0)의 개수를 세고, 익은 토마토(0일째 익은 토마토)는 q에 추가

2. q의 요소가 존재하지 않을때까지 다음과 같은 과정을 반복

    2-1. 날짜 1증가

    2-2. 해당 날짜에 익어있는 토마토의 개수만큼 다음을 반복

        2-2-1. q에서 토마토를 뺀다.

        2-2-2. 뺀 토마토의 주변 토마토 (총 6개의 방향) 중 익지 않은 토마토를 익게하고 q에 추가

3. 만약 익지 않았던 토마토의 개수가 익힌 토마토의 개수보다 많으면 -1출력

    그게 아니라면 날짜 출력

 

[풀이 코드_Java]

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;


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

public class Main {
	
	static int M, N, H;  
	static int ripe = 0;  // 익게 만든 토마토의 개수 
	
	static int[][][] box;
	static Queue<point> q = new LinkedList<>();
	
	static int[] dx = {-1, 1, 0, 0, 0, 0};
	static int[] dy = {0, 0, -1, 1, 0, 0};
	static int[] dz = {0, 0, 0, 0 , -1, 1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		H = sc.nextInt();
		box = new int[H][N][M];
		
		int unripe = 0;  // 익지 않은 토마토의 개수 
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N; j++) {   
				for (int k = 0; k < M; k++) {
					box[i][j][k] = sc.nextInt();
					
					if (box[i][j][k] == 0) unripe++;
					else if (box[i][j][k] == 1) {
						q.add(new point(i, j, k));
					}
					
				}
			}
		}
		
		int day = -1;
		while (!q.isEmpty()) {
			day += 1;
			
			int cnt = q.size();  // 하루동안 다른토마토에게 영향을 줄 익은 토마토의 개수 
			for (int i = 0; i < cnt; i++) {
				point cul = q.poll();
				runOneDay(cul.x, cul.y, cul.z);
			}
		}
		
		if (unripe > ripe) System.out.println(-1);
		else System.out.println(day);
		
	}
	
	public static void runOneDay(int x, int y, int z) {
		
		for (int i = 0; i < 6; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			
			if ((nx < 0 || nx >= H) || (ny < 0 || ny >= N) || (nz < 0 || nz >= M)) continue; // 범위를 벗어날경우 다음 방향으로 이동 
			if (box[nx][ny][nz] != 0) continue;  //익지않은 토마토가 아닐경우 다음 방향으로 이동
			
			ripe ++;
			box[nx][ny][nz] = 1;
			q.add(new point(nx, ny, nz));
			
		}
	}
}