[Baekjoon] 백준 7576번 : 토마토 (c++)

https://www.acmicpc.net/problem/7569

 

7569번: 토마토

 

이전에 풀었던 7576번 토마토와 비슷한 문제다.

2022.01.18 - [코딩테스트 연습/Baekjoon] - [Baekjoon]7576번 - 토마토

 

 

7576번 토마토에서 h(높이)가 추가된 문제였다.

3차원 배열과 함께 z축을 같이 쓰면 쉽게 해결되는 문제였다.

queue를 2중 pair로 선언해서 x, y, z 변수 세개를 사용했다.

 

---

​

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 101

int tomato[MAX][MAX][MAX];
int px[6] = { 0, 0, -1, 1, 0, 0 }; //상 하 좌 우 위 아래
int py[6] = { -1, 1, 0, 0, 0, 0 };
int pz[6] = { 0,  0, 0, 0, -1, 1 };
queue<pair<int, pair<int, int>>> q;
int cnt = -1;

void BFS(int N, int M, int H){
    
    //처음부터 익어있는 토마토는 큐에 다 넣고 시작함
    for(int i=0;i<H;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k<N;k++)
                if(tomato[i][j][k] == 1) q.push(make_pair(i, make_pair(j, k)));
        }
    }
    
    
    while (!q.empty()) {
        int q_size = q.size();
        cnt++;
        while (q_size--) {
            int z = q.front().first;
            int y = q.front().second.first;
            int x = q.front().second.second;
            q.pop();
            
            for(int i=0;i<6;i++){
                int dx = x + px[i];
                int dy = y + py[i];
                int dz = z + pz[i];
                
                if(dx < 0 || dx >= N || dy < 0 || dy >= M || dz < 0 || dz >= H
                  || tomato[dz][dy][dx] != 0 ) continue;
                
                tomato[dz][dy][dx] = 1;
                q.push(make_pair(dz, make_pair(dy, dx)));
                
                
            }
        }
        
       
    }
    
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N,M,H;
    cin >> N >> M >> H;
    memset(tomato, -1, MAX);
    for(int i=0;i<H;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k<N;k++)
                cin >> tomato[i][j][k];
        }
    }
    
    BFS(N, M, H);
    
    bool flag = false;
    //0이 하나라도 있을 경우 -1 출력
    for(int i=0;i<H;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k<N;k++)
                if(tomato[i][j][k] == 0) { flag = true; break; }
        }
    }
    
    if(flag) cout << "-1";
    else cout << cnt;
    return 0;
}