(C++) 백준 7569번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7569

7569번: 토마토

풀이

토마토(백준 7576번)의 3차원 버전이다.

2차원과 동일하게 진행하되 체크를 6개의 방향으로 진행하도록 BFS를 구현하면 된다.

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

using namespace std;

int dx[6] = {1,0,0,-1,0,0};
int dy[6] = {0,1,0,0,-1,0};
int dz[6] = {0,0,1,0,0,-1};
int brd[103][103][103];
int dst[103][103][103];
queue<tuple<int,int,int> > Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n, m, h;
    cin >> m >> n >> h;
    
    for(int k = 0; k < h; k++){ // 토마토 저장
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < m; j++){
                int tomato;
                cin >> tomato;
                if(tomato == 0) dst[i][j][k] = -1; // 익지 않은 토마토의 거리
                if(tomato == 1) Q.push({i, j, k}); // 익은 토마토부터 계산 시작하기 위해 큐에 넣기
                brd[i][j][k] = tomato;               
            }
        }
    }

    while(!Q.empty()){ // 익는데 걸리는 시간을 거리로 생각하여 dist에 저장
        auto cur = Q.front();
        Q.pop();
        int curX, curY, curZ;
        tie(curX, curY, curZ) = cur;
        int prev = dst[curX][curY][curZ]; // 현재 몇 일째인지
        for(int i = 0; i < 6; i++){
            int nx = curX + dx[i];
            int ny = curY + dy[i];
            int nz = curZ + dz[i];
            if (nx < 0 or nx >= n or ny < 0 or ny >= m or nz < 0 or nz >= h) continue; // 유효성 검사
            if (dst[nx][ny][nz] >= 0) continue; // 이미 계산됨
            dst[nx][ny][nz] = prev + 1;
            Q.push({nx, ny, nz});
        }
    }

    int mx = 0;
    for(int k = 0; k < h; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(dst[i][j][k] == -1) { // 익지 않은 토마토가 있다면
                    cout << -1;
                    return 0;
                }
                mx = max(mx, dst[i][j][k]);
            }
        }
    }
    cout << mx;
}