7569 토마토

문제 링크

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

풀이

3차원 배열의 각 칸에 처음 주어진 토마토들의 정보를 넣어준다. 이 때 익은 토마토(1)들은 queue에 넣어준 후, BFS를 실행하면 된다. BFS에서는 상하좌우를 확인해가며 인접한 칸에 안 익은 토마토(0)가 존재하는 경우 토마토를 익은 토마토로 업데이트 한다. 새롭게 토마토가 익은 칸의 값은 그 전 칸의 정수+1의 값으로 업데이트 해 준다.(날짜 계산하기 위함) 가장 오래 걸리는 경우를 알기 위해 변수 days를 만들어서 최댓값으로 계속 업데이트 한다. BFS가 종료되면 배열의 각 칸을 확인하면서 안 익은 토마토(0)이 존재하는 경우 -1을, 그렇지 않은 경우 days-1을 출력한다.

C++ 코드

#include <iostream>
#include <queue>

using namespace std;

int M, N, H;
int arr[100][100][100];

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

queue<int> q;
int days = 1;

void bfs(){
	int tmp[3];
	
	while(!q.empty()){
        for(int i=0; i<3; i++){
            tmp[i] = q.front();
            q.pop();
        }
        
        for(int i=0; i<6; i++){
            int nx = tmp[2] + dx[i];
            int ny = tmp[1] + dy[i];
            int nz = tmp[0] + dz[i];
            
            if(0<=nx && nx<M && 0<=ny && ny<N && 0<=nz && nz<H && arr[nz][ny][nx] == 0){
                q.push(nz);
                q.push(ny);
                q.push(nx);
                arr[nz][ny][nx] = arr[tmp[0]][tmp[1]][tmp[2]] + 1;
                if(days < arr[nz][ny][nx]) days = arr[nz][ny][nx];
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>M>>N>>H;
    
    for(int i=0; i<H; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<M; k++){
                cin>>arr[i][j][k];
                if(arr[i][j][k] == 1){
                	q.push(i);
                	q.push(j);
                	q.push(k);
				}
            }
        }
    }
    
    bfs();
    
    for(int i=0; i<H; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<M; k++){
                if(arr[i][j][k] == 0){cout<<-1<<endl;return 0;}
            }
        }
    }
    
    cout<<days-1<<endl;
    
    return 0;
}