[BOJ] 7569 토마토

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

7569번: 토마토

---

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

풀이

7576번 토마토 문제의 3차원 버전이다.

1. input을 받으면서 안익은 토마토 개수를 세고, 익은 토마토라면 위치를 큐에 넣는다.
2. 큐를 pop하면서 주위에 안익은 토마토가 있다면 그 토마토의 위치를 큐에 넣어주고 안익은 토마토 개수를 줄여준다. 또, 안익은 토마토를 익었다는 처리를 해준다.
3. 2번을 모든 토마토가 익었거나 큐가 비어질 때까지 반복한다.

조심해야 할 점은 input이 가로,세로,높이로 주어진다는 것이다. 보통 문제들은 세로,가로로 input을 주는데 문제를 잘 읽어야겠다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define p(a, b) make_pair(a, b)
#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

//3차원 배열이므로 6번 반복문을 돌아야 한다.
int dx[]={-1,1,0,0,0,0};
int dy[]={0,0,-1,1,0,0};
int dz[]={0,0,0,0,-1,1};

int info[100][100][100]; // 높이,세로,가로
int N,M,H;
int unripe=0;
queue<pair<int,pair<int,int> > > q;

void input() {
    // input이 가로,세로,높이 순으로 주어진다는 것을 주의하자
    cin>>M>>N>>H;
    for(int h=0;h<H;h++){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                cin>>info[h][i][j];
                if(info[h][i][j]==0) unripe++;
                else if(info[h][i][j]==1) q.push(p(h,p(i,j)));
            }
        }
    }
}

void init() {
}


void solution() {
    int x,y,z;
    int day=0;
    while(!q.empty()){
        int size=q.size();
        
        //만약 안익은 토마토가 더 이상 없다면 break
        if(unripe<=0) break;
        
        for(int j=0;j<size;j++){
            z=q.front().first,y=q.front().second.first,x=q.front().second.second; q.pop();
            for(int i=0;i<6;i++){
                int nz=z+dz[i],ny=y+dy[i],nx=x+dx[i];
                if(0<=nz&&nz<H&&0<=ny&&ny<N&&0<=nx&&nx<M&&info[nz][ny][nx]==0){
                    unripe--; // 안익은 토마토 개수를 줄인다
                    info[nz][ny][nx]=1; // 익은 토마토로 바꿔준다.
                    q.push(p(nz,p(ny,nx))); // 토마토 위치를 큐에 넣는다.
                }
            }
        }
        
        day++;
    }
    
    if(unripe!=0) cout<<-1; // 안익은 토마토가 존재하는 경우
    else cout<<day;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}