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

[문제]

7569번: 토마토 (acmicpc.net)

7569번: 토마토

[문제 풀이]

3차원 bfs 문제이다.

2차원에서 했던걸 응용해서 풀면 생각보다 쉽게 풀린다.

우선 모든 토마토를 입력받을 때 0이 하나도 없다면 0을 출력하고 종료해주자.

만약 토마토가 있다면 dx[4],dy[4],dh[2]를 이용해서 여섯방향으로 매번 큐에서 펼쳐져 나가면서 다음칸에 토마토가 있다면 해당 토마토를 익게 해주자.

그렇게 모든 작업이 끝나고 아직 0인 토마토가 있다면 -1을 출력 모든 토마토가 익었다면 제일 높은 값에서 -1 (-1을 하는 이유는 기본값이 1이기 때문에 다 익는데 걸리는 시간보다 1 높게 나오기 때문이다.)을 해주고 출력해주자.

[회고]

확실히 3차원 bfs 응용문제들을 이전에 풀고 와서인지 쉽게 풀렸다. 다만, 노가다성이 좀 있어서 코드를 짜는 작업이 생각보다 힘들었다.

[코드]

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

using namespace std;

queue<pair<int, pair<int, int> > > q;
int tomato[101][101][101];
int visited[101][101][101];
int n,m,h;
int total;

void bfs(){

    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    int dh[2] = {1,-1};

    while(q.size() > 0){
        int curH = q.front().first;
        int curX = q.front().second.first;
        int curY = q.front().second.second;
        q.pop();

        //2차원에서 하듯이 똑같이 해주자.
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 && nextX <n && nextY >= 0 & nextY <m){
                if(visited[nextX][nextY][curH] == 0){
                    if(tomato[nextX][nextY][curH] == 0){
                        tomato[nextX][nextY][curH] = tomato[curX][curY][curH] + 1;
                        visited[nextX][nextY][curH] = 1;
                        q.push(make_pair(curH,make_pair(nextX,nextY)));
                    }
                }
            }
        }
        //높이 양쪽이 되니 2차원에서 했던걸 응용해서 위아래를 추가하자.
        for(int i = 0;i<2;i++){
            int nextH = curH + dh[i];
            if(nextH >= 0 && nextH < h){
                if(visited[curX][curY][nextH] == 0){
                    if(tomato[curX][curY][nextH] == 0){
                        tomato[curX][curY][nextH] = tomato[curX][curY][curH] + 1;
                        visited[curX][curY][nextH] = 1;
                        q.push(make_pair(nextH,make_pair(curX,curY)));
                    }
                }
            }
        }
    }

    return;
}

int main(){
    cin>>m>>n>>h;
    for(int l = 0;l<h;l++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                cin>>tomato[i][j][l];
                if(tomato[i][j][l] == 0){
                    total++;
                }
                else if(tomato[i][j][l] == 1){
                    q.push(make_pair(l,make_pair(i,j)));
                }
            }
        }
    }
    if(total == 0){
        cout<<0<<endl;
        return 0;
    }
    bfs();
    
    int answer = 0;

    for(int l = 0;l<h;l++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(tomato[i][j][l] == 0){
                    cout<<-1<<endl;
                    return 0;
                }
                answer = max(answer, tomato[i][j][l]);
            }
        }
    }
    cout<<answer - 1<<endl;

    return 0;
}