BOJ 7569 - 토마토

www.acmicpc.net/problem/7569

7569번: 토마토

7569 번 문제는, 아래의

 

7576 번 토마토 문제

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

7576번: 토마토

와 다른점은 3차원 으로 한차원 높였다는 것이다. 

 

그래서 3차원 배열을 써야 풀 수 있다.

 

7576번을 이해 했다면, 7569번 문제도 별 문제 없이 통과 할 수 있다.

 

- c++

#include <iostream>
#include <queue>
#include <utility>
 
using namespace std;
 
int M, N, H, cnt;  // 열, 행, 높이, 일수 계산
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 adj[101][101][101];
queue<pair<pair<int, int>, int>> q;
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int z = q.front().second;
        q.pop();
 
        for (int i = 0; i < 6; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nz = z + dz[i];
            // 범위 안에 있으면서 익지 않은 토마토라면 기존값 대비 1 증가시켜서 익은 토마토로 바꾼다.
            if ((0 <= ny && ny < N) && (0 <= nx && nx < M) && (0 <= nz && nz < H) && adj[ny][nx][nz] == 0) {
                adj[ny][nx][nz] = adj[y][x][z] + 1;
                q.push(make_pair(make_pair(ny, nx), nz));
            }
        }
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(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 >> adj[j][k][i];
                if (adj[j][k][i] == 1) {
                    q.push(make_pair(make_pair(j, k), i));
                }
            }
        }
    }
 
    bfs();
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                if (adj[j][k][i] == 0) {
                    // 하나라도 익지 않은 토마토가 있다면 -1.
                    cout << "-1" << '\n';
                    return 0;
                }
 
                if (cnt < adj[j][k][i]) {
                    cnt = adj[j][k][i];
                }
            }
        }
    }
    
    // 토마토의 최초 값이 1부터 시작하므로 일 수는 하나 더 적은 값이 되야 함.
    cout << cnt - 1 << '\n';
 
    return 0;
}