[PS] 백준 7569번: 토마토

|

문제

내가 이해한 문제 내용

3차원으로 토마토가 주어질 때 토마토가 모두 익을 때까지 걸리는 최소일수를 구하여라.

접근 방식

예전에 2차원 토마토를 푼 적이 있기 때문에 전형적인 BFS로 앞/뒤/좌/우/위/아래를 점검하며 접근했다.

어려웠던 점 & 배운 점

3차원을 다루는 것이 좀 힘들었다. 또한 토마토를 모두 큐에 넣고 BFS를 돌려야 하는데 그 부분을 간과했다.

시간복잡도

$O(NMK)$

코드

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int m,n,h,_day,_x,_y,_z;
int tomato[101][101][101];

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

struct coor{
    int x;
    int y;
    int z;
    int day;
};

queue<coor> q;

int bfs()
{
    while(!q.empty()){
        coor cur = q.front(); q.pop();
        _day = cur.day;
        for(int i=0; i<6; i++){
            _x = cur.x+dx[i];
            _y = cur.y+dy[i];
            _z = cur.z+dz[i];
            if((_x>=n || _x<0)
            || (_y>=m || _y<0) 
            || (_z>=h || _z<0))
                continue;
            if(!tomato[_z][_x][_y]){
                tomato[_z][_x][_y] = 1;
                q.push({_x,_y,_z,_day+1});
            }
        }
    }
    return _day;
}


int main(void)
{
    scanf("%d%d%d",&m,&n,&h);
    for(int k=h-1; k>=0; k--){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++)
                scanf("%d",&tomato[k][i][j]);
        }
    }

    for(int k=0; k<h; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(tomato[k][i][j]==1)
                    q.push({i,j,k,0});
            }
        }
    }

    int ans = bfs();

    for(int k=h-1; k>=0; k--){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!tomato[k][i][j]){
                    printf("-1");
                    return 0;
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}