[백준] 7596번 토마토 (C)

출처

한국정보올림피아드 지역본선 2013 초등부 3번

문제 번호

백준 7569 토마토
코드업 :4773 토마토 (초등)

알고리즘

3차원 BFS

힌트

배열에 토마토가 익는 날짜를 저장

 

문제 풀이

이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. 3차원이기 때문에 방향 배열의 크기는 6*3이 된다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다.
BFS가 끝나고 day배열에 들어있는 최대값을 찾으면 된다. 만약 0이 남아 있다면 익지 않고 남아있는 토마토가 있는 것이기 때문에 ans를 0으로 바꿔주고 반복문을 탈출한다.day배열에 들어있는 숫자는 그 위치의 토마토가 익는 날 +1이기 때문에 우리가 구한 최대값에서 1을 빼고 출력을 해주어야 한다,

#include<iostream>
#include<queue>
using namespace std;
int day[100][100][100];


int n,m,h;
int dir[6][3]={{0,0,1},{0,1,0},{1,0,0},{-1,0,0},{0,-1,0},{0,0,-1}};

typedef struct dot{
    int x,y,z;
};

queue<dot> q;


int main(){

    cin>>n>>m>>h;

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

            }
        }
    }

    int date=2;
    while(!q.empty()){
        int size = q.size();
        for(int i=0;i<size;i++){

            int a=q.front().x,b=q.front().y,c=q.front().z;
            q.pop();

            for(int j=0;j<6;j++){
                int na=a+dir[j][0],nb=b+dir[j][1],nc=c+dir[j][2];
                if(na>=n||nb>=m||nc>=h||na<0||nb<0||nc<0||day[na][nb][nc]!=0)
                    continue;

                day[na][nb][nc]=date;
                q.push({na,nb,nc});
            }    
        }
        date++;
    }


    int ans=0, flag=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<n;k++){
                if(day[k][j][i]==0){
                    flag=1;
                    ans=0;
                    break;
                }
                ans=max(ans,day[k][j][i]);
            }
            if(flag)
                break;
        }
        if(flag)
            break;
    }
    cout<<ans-1;
}

백준

코드업