7569 토마토

토마토 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	14372	4911	3510	35.107%

문제

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

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

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

입력

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

출력

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

3차원 배열을 만들줄 몰라서 당황했던문제

평소 하던대로 했더니 풀렸다. 달라진점은 체크를 for문으로 한번 구현해봤다는것?

맞은사람중에 52등한 코드이다.

장점아닌 장점은 내 코드보다 속도가 빠른 사람중 나보다 메모리를 적게쓴사람은 2명이라는거?

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

struct Point{

    char z;

    char x;

    char y;

    

};

char tomato[101][101][101]; // z x y

bool visited[101][101][101];

queue<Point> que;

int m,n,h;

int num_of_visited=0;

int num_of_deep=0;

void bfs();

int main(){

    freopen("input.txt","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);

    memset(tomato, -1, sizeof(tomato));

    memset(visited, false, sizeof(visited));

    cin>>m>>n>>h;

    int temp;

    int how_many_m_one=0;

    int how_many_zero=0;

    int how_many_p_one=0;

    for(int i=0; i<h; ++i){

        for(int j=0; j<n; ++j){

            for(int k=0; k<m; ++k){

                cin>>temp;

                

                switch(temp){

                    case 1:

                        que.push({i,j,k});

                        //cout<<que.front().z<<" "<<que.front().x<<" "<<que.front().y<<"\n";

                        visited[i][j][k] = !visited[i][j][k];

                        tomato[i][j][k] = temp;

                        how_many_p_one++;

                        num_of_visited++;

                        break;

                    case 0:

                        how_many_zero++;

                        tomato[i][j][k] = temp;

                        break;

                    case -1:

                        how_many_m_one++;

                        break;

                    default:

                        break;

                }

            }

        }

    }

    if( how_many_p_one + how_many_m_one == n*m*h ){

        cout<<0;

        return 0;

    }

    bfs();

    //cout<<num_of_visited<<" "<<num_of_deep<<"\n";

    if( how_many_m_one + num_of_visited != n*m*h ){

        cout<<-1;

    } else {

        cout<<num_of_deep-1;

    }

    // cout<<"\n";

    // for(int i=0; i<h; ++i){

    //  for(int j=0; j<n; ++j){

    //      for(int k=0; k<m; ++k){

    //          cout<<visited[i][j][k]<<" ";

    //      }

    //      cout<<"\n";

    //  }

    //  cout<<"\n\n";

    // }

    return 0;

}

void bfs(){

    Point p;

    int size_of_deep = que.size();

    int cnt;

    

    short x_direction[6] = {-1,1,0,0,0,0};

    short y_direction[6] = {0,0,-1,1,0,0};

    short z_direction[6] = {0,0,0,0,-1,1};

    while(!que.empty()){

        cnt=0;

        for(int _s=0; _s<size_of_deep; ++_s){

            p = que.front();

            que.pop();

            

            for(int i=0; i<6; ++i){

                if( (p.x+x_direction[i] < n) && (p.x+x_direction[i] >=0) &&

                (p.y+y_direction[i] < m) && (p.y+y_direction[i] >=0) &&

                (p.z+z_direction[i] < h) && (p.z+z_direction[i] >=0) &&

                !visited[p.z+z_direction[i]][p.x+x_direction[i]][p.y+y_direction[i]] &&

                tomato[p.z+z_direction[i]][p.x+x_direction[i]][p.y+y_direction[i]] != -1 ){

                    

                    que.push({p.z+z_direction[i],p.x+x_direction[i],p.y+y_direction[i]});

                    visited[p.z+z_direction[i]][p.x+x_direction[i]][p.y+y_direction[i]] = !visited[p.z+z_direction[i]][p.x+x_direction[i]][p.y+y_direction[i]];

                    cnt++;

                }

            }

        }

        num_of_visited+= cnt;

        size_of_deep = cnt;

        num_of_deep++;

    }

}