문제

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

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

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

입력

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

출력

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

예제

예제 입력
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

예제 출력
-1

예제 입력
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

예제 출력
4

예제 입력
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

예제 출력
0

접근

  • 전형적인 BFS문제이다.
  • 7576 토마토의 업그레이드 버전이다.
    • if(7576을 풀었음) 방향만 추가해주면 풀리겠네!
    • else BFS를 어떻게 적용해야 할까?

내가 생각한 풀이

  • 하루에 한 번씩 토마토가 들어있는 칸을 모두 체크 한 후 문제에서 제시한 6방향을 체크하여 토마토가 있을시 Queue에 추가시킨다.
  • 토마토가 익을 수 있는지 없는지는 BFS가 끝난 후 토마토들의 상태를 계산하여 여부를 판단했다.

코드

#include<iostream>
#include<queue>
using namespace std;

int d[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}, map[101][101][101] = {0, }, check[101][101][101] = {0, }, dis[101][101][101] = {0, }, r = 0, xs,ys,hs;

//d배열이 방향을 나타내는 배열이다.
//map배열은 주어진 입력을 저장하는 배열, check는 검사를 했는지 안 했는지 확인할 배열, dis는 날짜를 저장하기 위한 배열이다.
//hs,xs,ys는 높이, 가로, 세로의 크기를 저장하기 위한 배열이다.
struct xyh{
  int h;
  int y;
  int x;
}; //토마토의 위치 정보를 가지고 있을 구조체
bool chk(int a, int b, int c){return (a>=0 && a<hs && b>=0 && b<ys && c>=0 && c<xs);} //배열의 접근을 잘못하여 런타임 에러가 발생할 경우를 대비하여 0보다 같거나 크고 최대값보다 작은지 체크한다.
queue<struct xyh> q;
void doBFS(){
  while(!q.empty()){
    struct xyh t = q.front();
    q.pop();
    check[t.h][t.y][t.x] = 1;
    for(int i = 0 ;i<6;i++){
      if(map[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]] == 0 && check[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]] == 0 && chk(t.h + d[i][0],t.y + d[i][1],t.x + d[i][2])){
      //map을 확인했을 때 그 자리에 토마토가 있고 체크가 아직 안 되었다면 q에 추가시키고 나머지 작업을 진행한다. (또한 위에서 설명한 chk 함수를 통해 적절한지 확인)
        q.push({t.h + d[i][0],t.y + d[i][1],t.x + + d[i][2]});
        check[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]] = 1;
        map[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]] = 1;
        dis[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]] = dis[t.h][t.y][t.x] + 1;
        if(dis[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]]>r) r = dis[t.h + d[i][0]][t.y + d[i][1]][t.x + d[i][2]]; //날짜가 더 커질 경우 바로 update
      }
    }
  }
}
int main(void){
  ios_base :: sync_with_stdio(false); cin.tie(NULL);
  cin>>xs>>ys>>hs;
  int sum = 0;
  for(int i = 0;i<hs;i++){
    for(int j = 0;j<ys;j++){
      for(int k = 0;k<xs;k++){
        cin>>map[i][j][k];
        if(map[i][j][k] != 0){
          sum++;
        }
      }
    }
  }
  if(sum == hs*ys*xs) cout<<0;
  else{
    for(int i = 0;i<hs;i++){
      for(int j = 0;j<ys;j++){
        for(int k = 0;k<xs;k++){
          if(map[i][j][k] != 1 || check[i][j][k] == 1) continue; //계속 안되다가 check조건을 추가해주니 성공...! 개이득~
          else q.push({i,j,k}); //한 번에 모든 토마토를 따져야 하므로 우선 queue에 모두 push
        }
      }
    }
    doBFS(); //그 후 BFS를 실행
    int sum = 0, minussum = 0;
    for(int i = 0;i<hs;i++){
      for(int j = 0;j<ys;j++){
        for(int k = 0;k<xs;k++){
          if(check[i][j][k] == 1) sum++;
          if(map[i][j][k] == -1) minussum++;
        }
      }
    }
    if(sum + minussum == hs*ys*xs) //BFS가 끝난 후 토마토가 다 익었는지 확인
      cout<<r;
    else cout<<-1;
  }
  return 0;
}