🧨문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
🧨입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
🧨출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
🧨접근방법
- 처음 익은 상태의 토마토를 list에 담아 둔다.
- bfs 돌기전에 list에 담아둔 토마토들을 queue에 옮긴다.
- bfs 과정에서 왼쪽 오른쪽 앞 뒤 위 아래를 확인 후 익지 않은 토마토 일 경우 익은 토마토로 바꾼후 해당하는 토마토 날수 +1과 좌표를 queue에 넣는다.
- queue가 빌때까지 3번과정을 반복한다.
- bfs 끝난 뒤 토마토 익은 여부를 확인 후 날수 또는 -1을 출력한다.
🧨코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int M,N,H;
static int[][][] map;
static int[] mx = {-1,1,0,0};
static int[] my = {0,0,-1,1};
static int[] mh = {1,-1};
static ArrayList<Node> list; // 처음에 익은 토마토들을 저장하기 위한 list
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
list = new ArrayList<>();
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H + 1][N + 1][M + 1];
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= N; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 1; k <= M; k++) {
map[i][j][k] = Integer.parseInt(st.nextToken());
if(map[i][j][k]==1){
list.add(new Node(i,j,k,0));
}
}
}
}
int answer = bfs();
if(check()){ // true이면 모든 토마토가 익은 상태이기 때문에 bfs을 통해 얻은 날 수를 출력
System.out.println(answer);
}else{ // false 이면 안익은 토마토가 있는 상태이기 때문에 -1 출력
System.out.println(-1);
}
}
// 모든 토마토가 익었는지 확인하는 메서드
static boolean check(){
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= M; k++) {
if(map[i][j][k]==0){
return false;
}
}
}
}
return true;
}
static int bfs(){
Queue<Node> queue = new LinkedList<>();
for(Node node : list) {
queue.add(node);
}
int count=0;
while(!queue.isEmpty()){
Node now = queue.poll();
// 앞 뒤 왼쪽 오른쪽 토마토를 확인하기 위한 코드
for(int i=0; i<4; i++){
int px = now.x + mx[i];
int py = now.y + my[i];
if(px>0 && py>0 && px<=N && py<=M){
if(map[now.h][px][py]==0){
map[now.h][px][py] = 1;
queue.add(new Node(now.h,px,py,now.day+1));
count = Math.max(count,now.day+1);
}
}
}
// 위 아래 토마토를 확인하기 위한 코드
for(int i=0; i<2; i++){
int ph = now.h + mh[i];
if(ph >0 && ph<=H){
if(map[ph][now.x][now.y]==0){
map[ph][now.x][now.y]=1;
queue.add(new Node(ph,now.x, now.y, now.day+1));
count = Math.max(count,now.day+1);
}
}
}
}
return count;
}
static class Node{
int h,x,y;
int day;
public Node(int h, int x, int y,int day) {
this.h = h;
this.x = x;
this.y = y;
this.day = day;
}
}
}
