[백준/C++] 7569번 토마토

문제: www.acmicpc.net/problem/7569

7569번: 토마토

 

 

문제풀이

 

같은 이름의 7576번 토마토 문제와 다른 점은 토마토가 3차원으로 주어진다는 것이다.

 

3차원 배열에 대하여 BFS를 진행하여 최단거리를 구하면 된다.

 

이때 토마토(1)가 주어진 곳의 좌표는 토마토가 익을 수 있는 시작점이므로 큐에 push 해준다.

 

 

코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int dz[6] = {-1,1,0,0,0,0}; //위, 아래 인접 토마토
int dx[6] = {0,0,-1,1,0,0}; //좌, 우
int dy[6] = {0,0,0,0,-1,1}; //앞, 뒤
int board[100][100][100];
int dist[100][100][100];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
   int m,n,h;
   cin>>m>>n>>h;

   for(int i=0; i<h; i++){
       for(int j=0; j<n; j++){
           fill(dist[i][j], dist[i][j]+m, -1);
       }
   }

    queue<tuple<int,int,int>> q;
   for(int i=0; i<h; i++){
       for(int j=0; j<n; j++){
           for(int k=0; k<m; k++){
               cin>>board[i][j][k];

               if(board[i][j][k] == 1){
                    q.push(make_tuple(i,j,k));
                    dist[i][j][k] = 0;
                }

               if(board[i][j][k] == -1)
                    dist[i][j][k] = 0;
           }
       }
   }

   while(!q.empty()){
       tuple<int,int,int> cur = q.front();
       q.pop();

       for(int dir=0; dir<6; dir++){
           int nz = get<0>(cur) + dz[dir];
           int nx = get<1>(cur) + dx[dir];
           int ny = get<2>(cur) + dy[dir];

           if(nz<0 || nz>=h || nx<0 || nx>=n || ny<0 || ny>=m) continue;
           if(dist[nz][nx][ny] >= 0) continue;

           dist[nz][nx][ny] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
           q.push(make_tuple(nz,nx,ny));
       }
   }

    int ans=0;
   for(int i=0; i<h; i++){
       for(int j=0; j<n; j++){
           for(int k=0; k<m; k++){
               if(dist[i][j][k] == -1){ //dist가 -1이면 익지않은 토마토가 있으므로
                   cout<<-1; //-1 출력
                   return 0;
               }

               ans = max(ans, dist[i][j][k]); //dist의 최댓값이 정답이다.
           }
       }
   }

   cout<<ans;

    return 0;
}

 

 

결과