[C++] 백준 7569:토마토

1. 문제

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

 

2. 문제 접근

문제를 요약하면 다음과 같다.

 

1. 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 총 6방향을 탐색해야 한다.
2. 익은 토마토는 익지 않은 토마토에 영향을 준다.
3. 한 상자에 들어있는 토마토가 모두 익는데까지 걸리는 기간을 출력한다.
4. 만약 배열에 저장될 때부터 모든 토마토가 익은 상태면 0, 모든 토마토가 익지 않은 상태면 -1을 출력한다.

 

이를 기반으로 문제를 풀어보자.

 

입력될 때부터 익은 토마토라면 q에 위치를 저장한다. 그리고 익은 토마토 위치에서부터 bfs 탐색을 시작하고, 만약 익지 않은 토마토가 인접해있다면 1로 바꾸어주고 tmp에 push 한다. 이때 tmp는 입력된 이후, 다른 토마토에 의해 익은 토마토가 된 것의 위치를 저장한다. 그리고 q가 빈 상태라면, 이후에 익은 상태가 된 토마토부터 다시 q에 push 한다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int m, n, h;
vector<vector<vector<int> > > arr;
queue<pair<pair<int, int>, int> > q;
queue<pair<pair<int, int>, int> > tmp;

int ans = 0;

// * 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향
int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };

void bfs(int x, int y, int z) {
    for (int i = 0; i < 6; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        int nz = z + dz[i];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h || arr[nx][ny][nz] != 0) continue; 

        if (arr[nx][ny][nz] == 0) { // * 익지 않음
            arr[nx][ny][nz] = 1;
            tmp.push(pair<pair<int,int>, int> ( pair<int, int> (nx,ny), nz) );
        }
    }
}

int main() {
    cin >> m >> n >> h;
    arr.resize(n, vector<vector<int> >(m, vector<int> (h)));

    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> arr[i][j][k];
                if (arr[i][j][k] == 1) { // * 익은 토마토인 경우
                    q.push(pair<pair<int,int>, int> (pair<int, int> (i,j), k));
                }
            }
        }
    }

    while(!q.empty()) {
        bfs(q.front().first.first, q.front().first.second, q.front().second);
        q.pop();

        if (q.empty()) {
            ans++;
            while (!tmp.empty()) {
                q.push(pair<pair<int,int>, int> ( pair<int, int> (tmp.front().first.first, tmp.front().first.second), tmp.front().second));
                tmp.pop();
            }
        }
    }

    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j][k] == 0) { // * 다 익지 않았음
                    cout << -1;
                    return 0;
                }
            }
        }
    }

    cout << ans - 1;
    return 0;
}