[Algorithm] 백준 토마토 7569 - C++, BFS

7569번: 토마토

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 101;

int m, n, h;
int totalTomato = 0;
int tomato[MAX][MAX][MAX];
int moveZ[] = { 0, 0, 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0, 0, 0 };
int moveX[] = { 0, 0, 1, -1, 0, 0 };

queue<pair<int, pair<int, int>>> q;

bool IsOut(int z, int y, int x){
    if(z < 0 || y < 0 || x < 0 || z >= h || y >= n || x >= m)
        return true;
    return false;
}
int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> m >> n >> h;
    for(int z = 0; z < h; z++){
        for(int y = 0; y < n; y++){
            for(int x = 0; x < m; x++){
                int input;
                cin >> input;
                tomato[z][y][x] = input;

                if(input == -1)    continue;

                if(input == 1){
                    q.push({z, {y, x}});
                }
                if(input == 0){
                    totalTomato++;
                }
            }
        }
    }

    if(totalTomato == 0){
        cout << "0\n";
        return 0;
    }

    //
    int makeCount = 0;
    int dayCount = 0;
    while (!q.empty()){
        int curDay = q.size();

        for(int day = 0; day < curDay; day++){
            int curZ = q.front().first;
            int curY = q.front().second.first;
            int curX = q.front().second.second;
            q.pop();

            for(int i = 0; i < 6; i++){
                int nextZ = curZ + moveZ[i];
                int nextY = curY + moveY[i];
                int nextX = curX + moveX[i];

                if(IsOut(nextZ, nextY, nextX))  continue;
                if(tomato[nextZ][nextY][nextX] != 0)    continue;

                tomato[nextZ][nextY][nextX] = 1;
                q.push({nextZ, {nextY, nextX}});
                makeCount++;
            }
        }
        dayCount++;
    }

    if(makeCount == totalTomato)
        cout << dayCount-1 << '\n';
    else 
        cout << "-1\n";

    return 0;
}

---

 기존 2차원 배열의 토마토 BFS 문제에서 차원이 하나 더 생긴 문제입니다. 단 이번에는 다 익힐 수 있다면 날짜를 구해야하는 문제로 조금 더 생각할 부분이 있었습니다.

                if(input == 1){
                    q.push({z, {y, x}});
                }
                if(input == 0){
                    totalTomato++;
                }

 input 에서 만일 익은 토마토라면 큐에 넣어주고 일반 토마토의 경우 갯수를 세 주었습니다. 계속 익은 정도를 확인하기에는 3차원에 최대 100 * 100 * 100 = 1000000을 탐색해야 하니 갯수를 미리 세 둬서 BFS가 끝났을 때 익힌 토마토 수와 익혀야 하는 토마토 수를 비교해 성공 여부를 판별할 생각입니다.

    while (!q.empty()){
        int curDay = q.size();

        for(int day = 0; day < curDay; day++){

 그리고 기존의 BFS 에서 날짜를 구하기 위해 현재 큐에 들어있는 토마토(오늘)을 구한뒤 이만큼 for문을 돌려 하루를 체크 했습니다.

     if(totalTomato == 0){
        cout << "0\n";
        return 0;
    }
    
    // BFS...
 
 if(makeCount == totalTomato)
        cout << dayCount-1 << '\n';
    else 
        cout << "-1\n";

 출력의 경우 BFS 전 익혀야할 토마토가 없다면 0을 출력해주고 있다면 탐색 후 위에 말한대로 값을 비교해 날짜를 출력하거나 실패의 의미인 -1을 표기하도록 했습니다.