[알고리즘 BFS & DFS 4] TOMATO

문제

---

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

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

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

 

입력

---

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

 

출력

---

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1 을 출력해야 한다.

 

예제 입력 1

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

예제 출력 1

-1

예제 입력 2

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

예제 출력 2

4

예제 입력 3

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1

예제 출력 3

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//백준 7569번
 
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
 
const int MAX = 105;
 
int arr[MAX][MAX][MAX];
int n,m,h;
 
//구조체 생성 (x좌표, y좌표, 높이, cnt값)
typedef struct coor{
  int x;
  int y;
  int h;
  int cnt;
  coor(){};
  coor(int _x, int _y, int _h, int _cnt) :
  x(_x), y(_y), h(_h), cnt(_cnt){};
}coor;
 
//구조체를 이용한 queue 생성
queue <coor> q;
 
//4방면 함수
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
 
//inside체크
bool inside(int x, int y){
  return (x<n && x>=0) && (y<m && y>=0);
}
 
void BFS(){
  if(q.empty()) return;
  int x = q.front().x;
  int y = q.front().y;
  int bfsH = q.front().h;
  int cnt = q.front().cnt;
  q.pop();
  
  
  //4방면 토마토 익히기
  int nx,ny;
  for(int i=0; i<4; i++){
    nx = x + dx[i];
    ny = y + dy[i];
    if(inside(nx,ny) && arr[nx][ny][bfsH]==0){
      arr[nx][ny][bfsH] = cnt+1;
      q.push(coor(nx,ny,bfsH,cnt+1));
    }
  }
  
  //위아래 토마토 익히기
  int plusH = bfsH+1;
  int minusH = bfsH-1;
  if(plusH<h && arr[x][y][plusH] == 0){
    arr[x][y][plusH] = cnt+1;
    q.push(coor(x,y,plusH,cnt+1));
  }
  if(minusH>=0 && arr[x][y][minusH] == 0){
    arr[x][y][minusH] = cnt+1;
    q.push(coor(x,y,minusH,cnt+1));
  }
  
  if(!q.empty()) BFS();
}
 
int main(){
  
  cin>>m>>n>>h;
  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<m; k++){
        cin>>arr[j][k][i];
        if(arr[j][k][i]==1){
          q.push(coor(j,k,i,1));
        }
      }
    }
  }
  
  BFS();
  
  //가장 큰 수 저장
  int maxSum = 0;
  //0이 하나라도 있으면 flag 1;
  int flag = 0;
  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<m; k++){
        if(arr[j][k][i]==0){
          flag = 1;
          break;
        }
        if(arr[j][k][i]>maxSum){
          maxSum = arr[j][k][i];
        }
      }
    }
  }
  
  if(flag == 1){
    cout<<"-1"<<endl;
  }else{
    cout<<maxSum-1<<endl;
  }
  
  
  //테스트 출력
  /*
  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<m; k++){
        cout<<arr[j][k][i]<<" ";
      }
      cout<<endl;
    }
    cout<<endl;
  }
  */
  
  return 0;
}