백준 7569 토마토

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 박스에 익은 토마토가 있을 때 앞뒤좌우상하의 안익은 토마토를 익게 만들어서 모든 토마토가 익는데 걸리는 날을 구하는 문제입니다.

 

전형적인 bfs 문제이므로 큐를 이용해서 진행해주면 됩니다. 다만 3차원이라서 조금 귀찮은 문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int tomato[101][101][101];
int nextx[6] = {1, -1, 0, 0, 0, 0};
int nexty[6] = {0, 0, 1, -1, 0, 0};
int nexth[6] = {0, 0, 0, 0, 1, -1};
int ans;

struct pos {
    int x,y,h;
};

queue<pos> q;
int M,N,H;

void bfs() {

    while(!q.empty()) {
        int n = q.size();
        bool flag = false;
        for(int i = 0; i < n; i++) {
            int x = q.front().x;
            int y = q.front().y;
            int h = q.front().h;

            q.pop();

            for(int j = 0; j < 6; j++) {
                int xx = x + nextx[j];
                int yy = y + nexty[j];
                int hh = h + nexth[j];

                if(xx < 0 || xx >= M || yy < 0 || yy >= N || hh < 0 || hh >= H)
                    continue;

                if(tomato[hh][yy][xx] == 0) {
                    tomato[hh][yy][xx] = 1;
                    q.push({xx,yy,hh});
                    flag = true;
                }
            }
        }
        if(flag)
            ans++;
    }

}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> M >> N >> H;
    bool zero = true;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < M; k++) {
                cin >> tomato[i][j][k];
                if(tomato[i][j][k] == 1)
                    q.push({k,j,i});
                if(tomato[i][j][k] == 0)
                    zero = false;

            }
    if(zero)
        cout<<0;
    else {
        bool flag = true;
        bfs();
        for(int i = 0; i < H; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < M; k++)
                    if(tomato[i][j][k] == 0)
                        flag = false;

        if(flag) cout<<ans;
        else cout<<-1<<'\n';
    }
    return 0;
}