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

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

 

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

int dh[6] = {0, 0, 0, 0, 1, -1};
int dn[6] = {1, -1, 0, 0, 0, 0};
int dm[6] = {0, 0, -1, 1, 0, 0};
vector<vector<vector<int>>> box;
int m, n, h;
int t = 0;

bool check() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (box[i][j][k] == 0) {
                    return false;
                }
            }
        }
    }
    return true;
}

void bfs() {
    queue<vector<int>> q;
    
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (box[i][j][k] == 1) {
                    q.push({i, j, k});
                }
            }
        }
    }

    while (!q.empty()) {
        int tmp = q.size();
        for (int i = 0; i < tmp; i++) {
            vector<int> cur = q.front();
            q.pop();
            for (int x = 0; x < 6; x++) {
                int ni = cur[0] + dh[x];
                int nj = cur[1] + dn[x];
                int nk = cur[2] + dm[x];
                if (ni >= 0 && ni < h && nj >= 0 && nj < n && nk >= 0 && nk < m && box[ni][nj][nk] == 0) {
                    q.push({ni, nj, nk});
                    box[ni][nj][nk] = 1;
                }
            }
        }
        t++;
        if (check()) {
            break;
        }
    }

    if (!check()) {
        t = -1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n >> h;
    box = vector<vector<vector<int>>>(h, vector<vector<int>>(n, vector<int>(m)));

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> box[i][j][k];
            }
        }
    }

    if (check()) {
        t = 0;
    }
    else {
        bfs();
    }

    cout << t << '\n';
}

문제를 보자마자 너비 우선 탐색 문제라는 것은 알 수 있었다. 다만 이제 3차원 벡터를 처음 써봐서 헤맨... (정답)

 

큐에서 하나를 꺼낼 때마다 t가 증가하는 것이 아니라 한 타임이 지날 때마다 t가 증가하도록 하려면? while문은 큐에 아무것도 없을 때까지 돌리고 그 안에 있는 for문은 그 순간에 큐에 들어있는 개수만큼 반복하도록 함. t는 for문이 끝날 때마다 증가시킴.

토마토가 전부 익었는지 확인하는 함수가 총 3번 쓰임. 1) 맨처음에 bfs 하기 전에(저장될 때부터 모든 토마토가 익어있는 상태), 2) 매 타임 지날 때마다, 3) 마지막에(토마토가 모두 익지 못하는 상황). ⇒ 따로 check()라는 함수로 만들어서 사용.

 

2024.05.14. 해결