[백준] BOJ 7569 토마토 (자바/3차원/BFS)

문제 유형 파악하기

 

다음과 같은 조건이 주어진다. 이때, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 하루가 지날 때마다 익은 토마토로 변한다는 조건으로 인해 전형적인 BFS 문제임을 파악했다.

 

또한, 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이라는 조건이 있는데, BFS 탐색하면서 이 방향에 대해 다 확인해 보면 됨을 느꼈다.

 

 

 

 

문제 풀이

1. 이 문제에서 핵심은 3차원 배열을 사용한다는 점이다. 처음에 3차원 배열을 사용해야 하는지 몰라서 애먹었다. 그래서 나는 3차원 배열을 선언하며 maps[높이][세로][가로]로 설정하여 문제를 풀었다. 

 

2. 큐에는 먼저 익은 토마토의 좌표를 전부 넣어 준 다음 BFS 탐색을 수행하였다.

 

3. BFS 탐색 시 안 익은 토마토인 경우에는 큐에 넣고 다음 탐색을 수행하면 된다.

 

 

 

 

 

---

 

 

구현

 

위의 여섯 방향의 조건을 탐색해보기 위해서 여섯 방향에 대한 배열을 만들어 두었다. 이때, [0]은 높이, [1]은 행, [2]는 열이다. 

static int[][] deltas = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, -1}, {0, 0, 1}}; 

 

package boj.p7569;

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

/*
 * boj 7569 토마토
 * */
public class Main_7569 {
	
	static int result;
	static int M,H,N;
	static int[][] deltas = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, -1}, {0, 0, 1}};
	static int[][][] maps;
	static int[][][] dayCount;//토마토가 익은 날짜
	
	
	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());
		
		maps = new int[H][N][M];
		dayCount = new int[H][N][M];
		Queue<int[]> queue = new LinkedList<>();
		
		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++) {
					maps[i][j][k] = Integer.parseInt(st.nextToken());
					if(maps[i][j][k] == 1) {
						queue.add(new int[] {i, j, k});
					}
				}
			}
		}
		
		
		if(check()) {
			result = 0;
		}else {
			if(queue.isEmpty()) result = -1;
			else {
				solve(queue);
				if(!check()) result = -1;
				else maxDay();
			}
		}
			
		System.out.println(result);
	}
	
	
	static void solve(Queue<int[]> queue) {
	
		while(!queue.isEmpty()) {
			int[] tmp = queue.poll();
			int nowHeight = tmp[0];
			int nowX = tmp[1];
			int nowY = tmp[2];
			
			if(check()) break;
			
			for (int dir = 0; dir < 6; dir++) {
				int nextX = nowX + deltas[dir][1];
				int nextY = nowY + deltas[dir][2];
				int nextHeight = nowHeight + deltas[dir][0];
				
				if(nextHeight < 0 || nextHeight >= H || nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || maps[nextHeight][nextX][nextY] == 1) continue;
				
				if(maps[nextHeight][nextX][nextY] == 0) {//안 익은 토마토인 경우
					maps[nextHeight][nextX][nextY] = 1;
					dayCount[nextHeight][nextX][nextY] = dayCount[nowHeight][nowX][nowY] + 1;
					queue.add(new int[] {nextHeight, nextX, nextY});
				}
			}
		}
	}
	
	/*
	 * 토마토가 익은 날짜 구함
	 * */
	static void maxDay() {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < M; k++) {
					result = Math.max(result, dayCount[i][j][k]);
				}
			}
		}
	}
	
	/*
	 * 토마토가 익어있는지 확인
	 * */
	static boolean check() {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < M; k++) {
					if(maps[i][j][k] == 0) return false;
				}
			}
		}
		//전부 익어있는 상태
		return true;
	}
	
}

 

 

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

7569번: 토마토