백준 7569 토마토 (C++)

7569번: 토마토

3차원 배열에 BFS를 사용하는 문제이다. 일반적인 BFS문제에 z축이 생겼다고 보면된다. 모든 토마토가 익어있을 경우를 찾기 위해 처음에 bool변수를 이용해주었다. 그리고 BFS함수를 보면 z축을 따로 추가하여 BFS를 수행해주면서 며칠째인지는 count를 통해 res로 넘겨주었다. 마지막으로 check함수를 통해 남은 익지않은 토마토가 존재하는지 확인 후 res값을 출력한다.
BFS만 안다면 쉽게 풀 수 있는 간단한 문제였다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int M, N, H, res = 0;
int A[100][100][100];
queue<pair<pair<int, int>, pair<int, int>>> q;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int dh[2] = { -1,1 };

bool check() {
    bool tf = false;
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (A[i][j][k] == 0) {
                    tf = true;
                }
            }
        }
    }

    return tf;
}

void bfs() {
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int h = q.front().second.first;
        int count = q.front().second.second;

        res = max(res, count);

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (A[ny][nx][h] == -1 || A[ny][nx][h] == 1) continue;

            A[ny][nx][h] = 1;
            q.push({ {ny,nx},{h,count + 1} });
        }

        for (int i = 0; i < 2; i++) {
            int nh = h + dh[i];

            if (nh < 0 || nh >= H) continue;
            if (A[y][x][nh] == -1 || A[y][x][nh] == 1) continue;

            A[y][x][nh] = 1;
            q.push({ {y,x},{nh,count + 1} });
        }
    }
}

void solution() {
    bfs();

    if (check()) {
        cout << -1;
    }
    else {
        cout << res;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> M >> N >> H;

    bool tf = false;
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> A[i][j][k];
                if (A[i][j][k] == 1) {
                    q.push({ { i,j }, {k,0} });
                }
                else if (A[i][j][k] == 0) {
                    tf = true;
                }
            }
        }
    }

    if (!tf) {
        cout << 0;
    }
    else {
        solution();
    }
    

    return 0;
}