[백준 7569] 토마토 (C++)

이 문제는 저번에 다뤘던 토마토 문제의 변형이다. 따라서, 익은 토마토의 근처부터 차례로 익어가므로 BFS 알고리즘으로 접근해야한다.

다만, 3차원이 되며 방향이 6개로 되었다는 점을 유의하며 접근해야 한다는 것을 잊지 말자.

따라서, 인접 위치를 구하려면 dx, dy, dz 테크닉으로 문제를 접근해야 한다.

그리고, 익은 토마토가 BFS의 시작점이 되기 때문에, 입력을 받으며 1인 지점을 큐에 삽입하였고, BFS를 진행하며 원본 데이터를 변형시키는 형태로 구현해보자.

여기서 주의해야할 점은 0이 존재하면 토마토가 모두 익지 못하는 상황이므로 -1을 출력하고 종료, 그렇지 않다면 최댓값 - 1을 출력하고 종료하면 된다. 출력값이 최댓값 - 1인 이유는 0일째에 익은 토마토가 배열에 1로 표현되므로 이것이 영향을 주어 다른 값들도 1씩 커졌기 때문이다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int m, n, h;
int storage[100][100][100];
queue<tuple<int, int, int>> q;
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    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 >> storage[i][j][k];
                if (storage[i][j][k] == 1) q.push({i, j, k});
            }
        }
    }
    
    while (!q.empty()) {
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
        
        for (int dir = 0; dir < 6; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir], nz = z + dz[dir];
            if (nx < 0 || nx >= h || ny < 0 || ny >= n || nz < 0 || nz >= m) continue;
            if (storage[nx][ny][nz]) continue;
            q.push({nx, ny, nz});
            storage[nx][ny][nz] = storage[x][y][z] + 1;
        }
    }
    
    int mx = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (!storage[i][j][k]) {
                    cout << -1;
                    return 0;
                }
                mx = max(mx, storage[i][j][k]);
            }
        }
    }
    cout << mx - 1;
}