[백준 7569] 토마토

 

 BFS 문제다. 이 문제는 포스트를 쓸까 말까 고민을 했다. 원래 포스트를 작성하면서 한 번 더 되뇌이는 용도로 작성해서, 너무 간단한 문제들은 굳이 포스트를 작성하지 않는데, 스탠다드 문제로 분류되어 있길래 그냥 작성하기로 했다.

 

 일반적인 BFS의 단순 차원 확장 문제다. 토마토의 상태 값을 이용해서 방문처리도 겸할 수 있으므로, 굳이 방문처리를 위한 배열을 생성할 필요도 없다.

 나는 BFS 내에서 이미 익은 토마토이면 그 노드에 대해서는 BFS 진행을 하지 않도록 했는데, 그러다보니 초기 값 처리를 따로 했다. 처음에 3차원 배열 값들을 입력받을 때, 익은 토마토 주위의 익지 않은 토마토들을 검색해서 큐에 넣어줘도 되고 익은 토마토 좌표들을 큐에 넣고 해당 좌표 값들을 -1로 변경해 두어도 된다. 나는 후자를 택했는데, 코드가 좀 더 지저분해져서 그렇지 전자가 미세하게 더 빠르긴 할 것 같다.

 그리고 C++에는 Triple과 같은 자료구조가 따로 없기 때문에, 구조체나 클래스를 하나 만드는 게 코드가 깔끔하게 나온다. 그 외에는 노드 깊이, 여기서는 며칠이 지났는지 나타내는 값을 큐에 함께 넣어서 정답을 찾아낼 때 쓰면 되고, 탐색이 끝났을 때도 익지 않은 토마토가 남았다면 -1을 출력하면 끝이다.

 

 문제 외적으로, 이번에는 오랜만에 bits/stdc++.h 헤더를 사용했는데, 확실히 컴파일 시간이 늘어지는 느낌이라 영 마음에 안 든다..

 

#include <bits/stdc++.h>

using namespace std;

int dx[6] = {1, 0, -1, 0, 0, 0};
int dy[6] = {0, 1, 0, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int m, n, h;

struct Point3d{
    int h, n, m;
};

bool isValid(int z, int y, int x) {
    return z>=0 && z<h && y>=0 && y<n && x>=0 && x<m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> h;

    vector<vector<vector<int> > > tomatoCube(h, vector<vector<int> >(n, vector<int>(m)));
    queue<pair<Point3d, int> > q;
    int remainTomato = 0;

    for(int i=0; i<h; i++) {
        for(int j=0; j<n; j++) {
            for(int k=0; k<m; k++) {
                cin >> tomatoCube[i][j][k];
                if(tomatoCube[i][j][k]==0 || tomatoCube[i][j][k]==1) {
                    remainTomato++;
                }
                if(tomatoCube[i][j][k]==1) {
                    // BFS 초기값 처리용
                    tomatoCube[i][j][k] = -1;
                    q.push({{i, j, k}, 0});
                }
            }
        }
    }

    int day = 0;

    while(!q.empty()) {
        auto p = q.front().first;
        int curDay = q.front().second;
        q.pop();
        if(tomatoCube[p.h][p.n][p.m]==1) continue;
        day = curDay;
        remainTomato--;
        tomatoCube[p.h][p.n][p.m] = 1;
        for(int i=0; i<6; i++) {
            int nextZ = p.h+dz[i];
            int nextY = p.n+dy[i];
            int nextX = p.m+dx[i];
            if(isValid(nextZ, nextY, nextX) && tomatoCube[nextZ][nextY][nextX]==0) {
                q.push({{nextZ, nextY, nextX}, curDay+1});
            }
        }
    }

    if(remainTomato==0) {
        cout << day;
    } else {
        cout << -1;
    }
}