BOJ7569 토마토

<Solution>

1. 익은 토마토들은 하루 지나면 인접 토마토를 익게함(인접 : 위,아래,오,왼,상,하)

2. 토마토가 다 익는데 걸리는 최소 일 수

3. 동시간대 퍼지는 토마토인지 어떤식으로 구분할 수 있을까?? 큐의 크기로 구분

---

<Source Code>

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 BOJ7569_토마토 {

	static int[][][] map;
	static int day = 0;
	static int[][][] visit;
	static int M;
	static int N;
	static int H;
	static int zero_cnt;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		map = new int[H][N][M];
		visit = new int[H][N][M];
		zero_cnt = 0; // 종료조건으로 사용 가능
		for(int hi = 0; hi < H; hi++) {
			for(int ni = 0; ni < N; ni++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int mi = 0; mi < M; mi++) {
					int temp_n = Integer.parseInt(st.nextToken());
					map[hi][ni][mi] = temp_n;
					if(temp_n == 0)
						zero_cnt++;
					else if(temp_n == 1) // 익은 토마토들의 위치 저장
						q.add(new pair(hi,ni,mi));
				}
			}
		}
		// 익게할 토마토가 한개도 없으면 그냥 끝
		if(zero_cnt == 0) {
			System.out.print(0);
			return;
		}
		// 다 안익은 토마토 일때
		else if(zero_cnt == H * M * N) {
			System.out.print(-1);
			return;
		}
		bfs();
		if(zero_cnt > 0)
			System.out.print(-1);
		else
			System.out.print(day);
	}
	// 상,우,하,좌,위,아래
	static int[] dh = {0,0,0,0,-1,1};
	static int[] dn = {-1,0,1,0,0,0};
	static int[] dm = {0,1,0,-1,0,0};
	static Queue<pair> q = new LinkedList<pair>();
	public static void bfs() {
		while(!q.isEmpty()) {
			int q_size = q.size();
			day++;
			for(int qi = 0; qi < q_size; qi++) {
				pair p = q.poll();
				int ph = p.h;
				int pn = p.n;
				int pm = p.m;
				for(int hnmi = 0; hnmi < 6; hnmi++) {
					int hh = ph + dh[hnmi];
					int nn = pn + dn[hnmi];
					int mm = pm + dm[hnmi];
					if(hh < 0 || hh >= H || nn < 0 || nn >= N || mm < 0 || mm >= M)
						continue;
					if(map[hh][nn][mm] != 0)
						continue;
					q.add(new pair(hh, nn, mm));
					map[hh][nn][mm] = 1;
					zero_cnt--; // 안익은 토마토를 익은 상태로 만드니깐 0의 개수를 줄여줌
					if(zero_cnt == 0) // 다 익었으면 더 이상 볼필요 없으니 return
						return;
				}
			}
		}
	}

	static class pair{
		int h;
		int n;
		int m;
		public pair(int h, int n, int m) {
			super();
			this.h = h;
			this.n = n;
			this.m = m;
		}
	}
}

처음에는 3중 for 문 돌면서 익은 토마토가 있을 때 마다 bfs를 돌렸는데 이러면 안되고 처음에 익은 토마토의 위치를 일괄 저장해주고 bfs 한번 타고 들어가는 식으로 해야함