백준[7569] - 토마토2

문제

백준 7569 문제 보기

접근 방법

7576번 문제와 동일하지만 다른 점은 아래와 위까지 진행된다는 점이다. 이전 토마토 문제와 같이 bfs를 활용하되 토마토 배열을 3차원으로 활용하여 위, 아래면까지 검사를 진행한다.

코드

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

using namespace std;

int M, N, H;
int map[105][105][105];
int rr[4] = {-1 , 0, 1, 0};
int cc[4] = {0, 1, 0, -1};

struct tomato {
    int r;
    int c;
    int h;
    int cnt;
};

queue<tomato> q;

int main() {
    cin >> M >> N >> H;

    for(int h = 0; h < H; h++) {
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < M; j ++) {
                cin >> map[i][j][h];
                // 토마토가 있는 위치를 큐에 넣음
                if(map[i][j][h] == 1) {
                    q.push({i, j, h, 0});
                }
            }
        }
    }
    int ans = -1;
    while(!q.empty()) {
        int r = q.front().r;
        int c = q.front().c;
        int h = q.front().h;
        int cnt = q.front().cnt;
        // 가장 큰값을 유지
        ans = max(ans, cnt);
        q.pop();
        // 북, 동, 남, 서 방향의 토마토
        for(int i = 0; i < 4; i ++) {
            int nextR = r + rr[i];
            int nextC = c + cc[i];
            if(nextR >= 0 && nextC >= 0 && nextC < M && nextR < N && map[nextR][nextC][h] == 0) {
                map[nextR][nextC][h] = 1;
                q.push({nextR, nextC, h, cnt + 1});
            }
        }
        int up = h + 1;
        int down = h - 1;
        // 윗 상자 토마토
        if(up < H) {
            if(map[r][c][up] == 0) {
                map[r][c][up] = 1;
                q.push({r, c, up, cnt + 1});
            }
        }
        // 아랫 상자 토마토
        if(down >= 0) {
            if(map[r][c][down] == 0) {
                map[r][c][down] = 1;
                q.push({r, c, down, cnt + 1});
            }
        }
    }

    // 익지않은 토마토 검사
    for(int h = 0; h < H; h++) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (map[i][j][h] == 0) {
                    cout << -1 << '\n';
                    return 0;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}