[Day 4] 백준 7569 : 토마토

해법 : 3차원 bfs

정보올림피아드 2013 초등본선 3번 문제인데

이 당시에 본선에서 문제를 풀 때.. 그냥 배열로 3차원을 구현할 수 있을지 몰랐어서.. 당황했던 기억이 난다.

사실 그냥 2차원에서처럼 3차원에 적용해서 풀어주면 된다. 

유의할 점은 for 문을 작성할 때 행, 열, 차원 순서가 아니라 차원, 열, 행 순서로 작성해야 한다는 점 정도 인듯.

 

 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n,m,h;
int A[105][105][105];
int vt[105][105][105];
struct tuple2 {
    int x,y,z;
    int val;
};
vector <tuple2> que;
int r,f;
int ans;
int _x[6]={0,0,0,0,1,-1};
int _y[6]={0,0,1,-1,0,0};
int _z[6]={1,-1,0,0,0,0};
void bfs() {
    tuple2 srg,srg2;
    int X,Y,Z,i;
    do {
        srg=que[f++];
        ans=max(ans,srg.val);
        for(i=0;i<6;i++) {
            X=srg.x+_x[i];
            Y=srg.y+_y[i];
            Z=srg.z+_z[i];
            if(X<0 || X>=h || Y<0 || Y>=m || Z<0 || Z>=n) continue;
            if(A[X][Y][Z]==0 && vt[X][Y][Z]==0) {
                srg2.x=X;
                srg2.y=Y;
                srg2.z=Z;
                srg2.val=srg.val+1;
                vt[X][Y][Z]=1;
                A[X][Y][Z]=1;
                r++;
                que.push_back(srg2);
            }
        }
    } while(r>f);
    int flag=0;
    int j,k;
    for(i=0;i<h;i++) {
        for(j=0;j<m;j++) {
            for(k=0;k<n;k++) {
                if(A[i][j][k]==0) {
                    flag=1;
                    break;
                }
            }
        }
    }
    if(flag==1) printf("-1\n");
    else printf("%d\n",ans);
}
int main() {
    //freopen("input.txt","r",stdin);
    scanf("%d %d %d",&n,&m,&h);
    int i,j,k;
    int flag=0;
    tuple2 srg;
    for(i=0;i<h;i++) {
        for(j=0;j<m;j++) {
            for(k=0;k<n;k++) {
                scanf("%d",&A[i][j][k]);
                if(A[i][j][k]==0) flag=1;
                if(A[i][j][k]==1) {
                    vt[i][j][k]=1;
                    srg.x=i;
                    srg.y=j;
                    srg.z=k;
                    srg.val=0;
                    r++;
                    que.push_back(srg);
                }
            }
        }
    }
    if(flag==0) printf("0\n");
    else bfs();
    return 0;
}