[백준/c++] 7569번: 토마토

 

 

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

7569번: 토마토

 

 

처음에 문제 보고 정말 풀기 싫게 생겨서 겁먹었는데 차근차근 읽어보니 생각보다 쉬운 문제였다.

3차원 배열로 BFS 탐색하면서 날짜를 카운팅 하면 된다. 3차원이다 보니 h, r, c 가 헷갈리기 쉬운데 또 막상 해보면 할만하다.

BFS의 while문으로 토마토를 탐색하면서 익혀주고, 익지 않은 토마토 있는지 체크하는 부분도 따로 만들어줬다.

 

이렇게 확산되는 문제는 DFS보다는 BFS를 사용하면 좋은데, BFS를 사용하면서 multi-source(multi-root) 즉, 시작점을 모두 queue에 털어 넣고 시작하면 된다. 그럼 여러 시작점이 확산되기 때문!

 

 

#include <iostream>
#include <queue>
#define MAX 120
using namespace std;

int H, C, R;
int box[MAX][MAX][MAX];
int dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}}; //위,아래,좌,우,뒤,앞 - H,R,C
queue<pair<pair<int, int>, int>> q; //H,R,C

void BFS(){
    int days = 0;
    
    //토마토 탐색
    while(!q.empty()){
        int size = q.size();
        days++;
        for(int i=0; i<size; i++){
            int h = q.front().second;
            int r = q.front().first.first;
            int c = q.front().first.second;
            q.pop();
            
            for(int j=0; j<6; j++){
                int dh = h + dir[j][0];
                int dr = r + dir[j][1];
                int dc = c + dir[j][2];
                
                if(dh < H && dr < R && dc < C && dh >= 0 && dc >= 0 && dr >= 0 && box[dh][dr][dc] == 0){
                    box[dh][dr][dc] = 1; //익은 토마토로 바꿔주기
                    q.push({{dr, dc}, dh}); //queue에 넣기
                }
            }
        }
    }

    
    //익지 않은 토마토 있는지 체크 (보관후 하루 지나야 익음)
    for(int i=0; i<H; i++){
        for(int j=0; j<R; j++){
            for(int k=0; k<C; k++){
                if(box[i][j][k] == 0){
                    cout << -1 << '\n';
                    return;
                }
            }
        }
    }
    cout << days-1 << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> C >> R >> H;
    for(int i=0; i<H; i++){
        for(int j=0; j<R; j++){
            for(int k=0; k<C; k++){
                cin >> box[i][j][k];
                //multi-bfs(multi-root/source) - 시작점 몽땅 넣어주기
                if(box[i][j][k] == 1) q.push({{j, k}, i}); //R,C,H
            }
        }
    }
    BFS();
    return 0;
}