[백준_7569번] 토마토

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

7569번: 토마토

[문제]

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

 

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

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

 

[입력 조건]

 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

[코드]

import java.util.*;

class Tomato {
	int x; // 세로
	int y; // 가로 
	int z; // 높이
	
	public Tomato(int z, int x, int y) {
		this.x=x;
		this.y=y;
		this.z=z;
	}
}
public class BaekJoon_7569 {
	public static int[][][] board;
	public static int n,m,h;
	public static int dx[] = {-1, 0, 1, 0, 0, 0}; // 상,하,좌,우,위,아래
	public static int dy[] = {0, 1, 0, -1, 0, 0};
	public static int dz[] = {0, 0, 0, 0, 1, -1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		m=sc.nextInt(); // 가로
		n=sc.nextInt(); // 세로
		h=sc.nextInt(); // 높이
		board=new int[h][n][m];
		
		for(int k=0;k<h;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					board[k][i][j]=sc.nextInt();
				}
			}
		}

		/*
		 * bfs의 시작 인덱스는 주어지지 않는다. 
		 * 이번 문제는 익은 토마토 지점으로부터 6방향을 탐색해야하기 때문에
		 * 아래 bfs() 함수에서 익은 토마토 좌표를 큐에 삽입하는 과정을 수행한다.
		 */
		bfs();
	}
	public static void bfs() {
		Queue<Tomato> q=new LinkedList<>();
		
		// 익은 토마토의 좌표를 큐에 삽입한다.
		for(int k=0;k<h;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(board[k][i][j]==1)
						q.offer(new Tomato(k,i,j));
				}
			}
		}
		
		while(!q.isEmpty()) {
			Tomato tomato=q.poll();
			int x=tomato.x;
			int y=tomato.y;
			int z=tomato.z;
			
			// 익은 토마로를 기점으로 상,하,좌,우,위,아래 6방향을 탐색한다.
			for(int i=0;i<6;i++) {
				// 다음 위치 계산
				int nx=x+dx[i];
				int ny=y+dy[i];
				int nz=z+dz[i];
				
				// 범위를 벗어났으면 넘어간다.
				if(nx>=n||ny>=m||nz>=h||nx<0||ny<0||nz<0)
					continue;
				// 새로 계산한 위치에 익은 토마토가 없다면 넘어간다.
				if(board[nz][nx][ny]!=0)
					continue;
				
				// 총 일수를 구해야하기 때문에 현재 일수 +1을 해준다.
				board[nz][nx][ny]=board[z][x][y]+1;
				// 새로운 익은 토마토의 위치를 큐에 삽입한다.
				q.add(new Tomato(nz,nx,ny));
			}
		}
		
		// 최대 일수 구하기
		int max=Integer.MIN_VALUE;
		for(int k=0;k<h;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					// 토마토가 모두 익지 못한 상황이라면 -1 return 
					if(board[k][i][j]==0) {
						System.out.println(-1);
						return;
					}
					// 갱신한 board에서 최댓값 찾기
					max=Math.max(max, board[k][i][j]);
				}
			}
		}
		// 최대 일수는 최댓값 -1이 된다.
		System.out.println(max-1);
	}
}

 

[고찰]

 이번 문제는 이전 7576 토마토 문제를 풀어봤기 때문에 쉽게 풀 수 있었다. 앞선 문제와 다른 점은 높이가 추가됐기 때문에 탐색해야하는 방향이 4방향에서 6방향으로 늘어났다는 것이다. 따라서 탐색 부분에서 for문이 하나 추가된것 말고는 같게 풀면 정답 처리를 받을 수 있는 문제였다.