[BOJ] 백준 7569 토마토 (JAVA/자바) - BFS

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

7569번: 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

풀이

매번 풀던 4방향 탐색에서 6방향으로만 바꿔주면 된다.

1. static class 선언 시, height를 추가

	static class Point {
		int h, i, j;

		Point(int h, int i, int j) {
			this.i = i;
			this.j = j;
			this.h = h;
		}
	}

2. 방향 전환을 위한 변수 저장

	static int[] di = { 1, -1, 0, 0, 0, 0 };
	static int[] dj = { 0, 0, 1, -1, 0, 0 };
	static int[] dh = { 0, 0, 0, 0, 1, -1 };

3. bfs() 함수

(1) "하루가 지나면" 이라는 조건이 있으므로, 토마토가 번져 익어가는 날을 세기 위해 맨 첫날 익은 토마토를 Q에 먼저 넣어주고

(2) 익지 않은 토마토를 센다.

		for (int h = 0; h < H; h++) {
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[h][i][j] = Integer.parseInt(st.nextToken());
					if (map[h][i][j] == 1)
						Q.add(new Point(h, i, j));
					else if (map[h][i][j] == 0)
						unripe++;
				}
			}

(3) 그 날 익은 토마토들만 영향을 줄 수 있도록 Q size를 재서 for문을 돌려주고, 영향을 받아 익은 토마토가 있다면 익지 않은 토마토의 개수 - 1

(4) 그 날 하루가 끝나면 answer 증가

	public static void bfs() {

		while (!Q.isEmpty()) {
			int size = Q.size();

			for (int s = 0; s < size; s++) {
				Point cur = Q.poll();
				for (int d = 0; d < 6; d++) {
					int ni = cur.i + di[d];
					int nj = cur.j + dj[d];
					int nh = cur.h + dh[d];

					if (ni < 0 || nj < 0 || nh < 0 || ni >= N || nj >= M || nh >= H)
						continue;
					if (map[nh][ni][nj] == -1)
						continue;
					if (visit[nh][ni][nj] == 1)
						continue;
					if (map[nh][ni][nj] == 0) {
						Q.add(new Point(nh, ni, nj));
						visit[nh][ni][nj] = 1;
						unripe--;
					}
				}
			}
			answer++;
		}
	}

- 모든 토마토가 익고 나서도 answer++가 되므로 최종 출력에서 -1을 해줌

- 익지 않은 토마토가 남아 있다면 -1 출력

			System.out.println(unripe > 0 ? -1 : answer - 1); // 모든 토마토가 익고 나서도 answer++가 되므로

 

 

최종 코드

package bfs;

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

public class BOJ_7569_토마토 {
	static class Point {
		int h, i, j;

		Point(int h, int i, int j) {
			this.i = i;
			this.j = j;
			this.h = h;
		}
	}

	static int[] di = { 1, -1, 0, 0, 0, 0 };
	static int[] dj = { 0, 0, 1, -1, 0, 0 };
	static int[] dh = { 0, 0, 0, 0, 1, -1 };
	static int M, N, H;
	static int[][][] visit, map; // 높이, 가로 세로
	static Queue<Point> Q;
	static int unripe, answer;
	public static void main(String[] args) throws Exception {
		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());

		visit = new int[H][N][M];
		map = new int[H][N][M];
		unripe = 0;
		Q = new LinkedList<>();
		for (int h = 0; h < H; h++) {
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[h][i][j] = Integer.parseInt(st.nextToken());
					if (map[h][i][j] == 1)
						Q.add(new Point(h, i, j));
					else if (map[h][i][j] == 0)
						unripe++;
				}
			}
		}
		if (unripe == 0) {
			System.out.print(0);
		} else {
			bfs();
			System.out.println(unripe > 0 ? -1 : answer - 1); // 모든 토마토가 익고 나서도 answer++가 되므로
		}

	}

	public static void bfs() {

		while (!Q.isEmpty()) {
			int size = Q.size();

			for (int s = 0; s < size; s++) {
				Point cur = Q.poll();
				for (int d = 0; d < 6; d++) {
					int ni = cur.i + di[d];
					int nj = cur.j + dj[d];
					int nh = cur.h + dh[d];

					if (ni < 0 || nj < 0 || nh < 0 || ni >= N || nj >= M || nh >= H)
						continue;
					if (map[nh][ni][nj] == -1)
						continue;
					if (visit[nh][ni][nj] == 1)
						continue;
					if (map[nh][ni][nj] == 0) {
						Q.add(new Point(nh, ni, nj));
						visit[nh][ni][nj] = 1;
						unripe--;
					}
				}
			}
			answer++;
		}
	}
}