[BaekJoon/백준] 7569번 토마토

 

7576번 토마토와 매우 동일한 유형이다.

 

7576번은 2차원,

7569번은 3차원이라는 점에서 차이만 있을 뿐이다.

 

 

입력을 받으면서, 1인 입력을 받을 때 전부 큐에 넣어준다. 

 

그리고, 입력을 다 받았으면 큐를 대상으로 bfs를 시작해주면 된다.

 

익은 토마토(1) 들을 기점으로, bfs 탐색이 시작될 것이다!

 

탐색을 하면서, 너비가 증가할 때 마다 현재 배열 값에서 + 1을 해준다.

이는 며칠이 지났는지의 의미를 갖게 하기 위해서다.

// 토마토가 들어있지 않을 수도 있음을 주의

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M, H;


int BOX[100][100][100];
bool VISIT[100][100][100];


int mx[6] = {0, 0, 1, -1, 0, 0};
int my[6] = {1, -1, 0, 0, 0, 0};
int mz[6] = {0, 0, 0, 0, 1, -1};



// queue<pair<int, pair<int, int>>> 하던가
// queue<vector<int>> 하던가
// 선택해서, 세 개의 좌표를 받아내도록.
queue<vector<int>> que; // 문제 특성상, 큐 선언문이 바깥에. 1인것을 전부 큐에 집어넣은 다음에 bfs 시작해야하므로.


void bfs() {
        
    
    while(!que.empty()) {
        
        int z = que.front()[0];
        int x = que.front()[1];
        int y = que.front()[2];
        
        que.pop();
        
        
        for(int i = 0; i < 6; i++) {
            
            int tz = z + mz[i];
            int tx = x + mx[i];
            int ty = y + my[i];
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M || tz < 0 || tz >= H)
                continue;
            
            
            if(!VISIT[tz][tx][ty] && BOX[tz][tx][ty] == 0) {
                
                vector<int> v = {tz, tx, ty};
                
                que.push(v);
                VISIT[tz][tx][ty] = true;
                
                BOX[tz][tx][ty] = BOX[z][x][y] + 1; // 걸리는 날짜 계산
            }
            
        }
        
    }
    
}



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 >> BOX[i][j][k];
                
                // 1이라면 = 익은 토마토라면 큐에 담아둠.
                if(BOX[i][j][k] == 1) {
                    
                    vector<int> v = {i, j, k};
                    que.push(v);
                    VISIT[v[0]][v[1]][v[2]] = true;
                }
                
            }
        }
        
    }
    
    
    // 3차원에 할당 완료.
    
    // 넣어둔 1들을 토대로 bfs 시작.
    bfs();
    
    
    // if 0이 아직 있다면, 다 익을 수 없는 거
    // else if 최댓값이 1이라면 처음부터 다 익은 것.
    // else 최댓값이, 모두 익는데 걸린 날짜임.
    
    int MAX = -1;
    for(int i = 0; i < H; i++) {
        
        
        for(int j = 0; j < N; j++) {
            
            
            for(int k = 0; k < M; k++) {
                
                if(BOX[i][j][k] == 0) {
                    cout << "-1\n";
                    exit(0);
                }

                if(MAX < BOX[i][j][k])
                    MAX = BOX[i][j][k];
            
            }
        }
    }
    
    cout << ((MAX == 1) ? 0 : MAX - 1) << "\n";
}

 

 

소요 시간 : 40분