[ 백준 7569 ] 토마토 (C++)

백준의 토마토(7569) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 토마토(7576)번과 매우 유사한 문제이다.

- 입력으로 토마토가 담긴 상자의 가로, 세로, 높이가 주어지고, 가로 세로 높이에 알맞게 토마토 상자의 현재 상태가 주어진

  다. 1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어있지 않은 칸을 의미한다.

- 익은 토마토는 상하좌우위아래 중 한방향으로라도 익지 않은 토마토가 있으면, 그 방향에 있는 토마토를 익게 만들 수 있다.

- 모든 토마토가 다 익으려면 최소 몇일이 필요한지 구하는 문제이다.

[ 문제풀이 ]

1. 문제에 조건이 하나 있다. 처음 저장될 때 부터 모든 토마토가 익어 있는 상태이면 0을 출력해라 ! 라는 조건이다. 이 조건

   을 먼저 해결하기 위해서, 입력 받을 때 0을 하나라도 입력 받으면 표시를 해줄 수 있는 변수를 하나 사용하였다.

   0을 입력받는 순간, true였던 변수의 값이 false로 바뀌게 설정해 주었고, 이를 통해 위의 조건을 해결할 수 있다.

2. 토마토가 있는 위치를 입력받으면서 모두 Queue에 넣어 주었다. 그 상태에서 BFS를 실행시키면서, BFS Leveling Skill을 

   통해 날짜를 계산해 주었다. (사실 날짜를 Count하는 방법은 여러가지가 있지만 여기서는 Queue의 Size를 이용하였다.)

   2-1) BFS를 구현할 때, 밑의 코드를 참고하면서 보면 알겠지만, While문이 반복될 때마다 Queue의 Size를 저장한 후에,

         그 Size만큼만 반복시키면서, 날짜를 Count해 주었다. 

   2-2) 예를 들어 2-1)의 말을 구체적으로 설명해 보자면, 문제에서 주어진 예제입력 2번에서 1이 있는 지점에서부터

         2칸위에 1이 하나 더 있다고 가정해보자. 

          0 0 0 0 0

          0 0 1 0 0

          0 0 0 0 0      

          0 0 0 0 0

          0 0 1 0 0

          0 0 0 0 0     (이런 경우를 예를들어서 설명해보겠다)

         그렇게 되면 맵에는 MAP[1][2][0] 과 MAP[1][2][1] (MAP[x][y][층]) 

         총 2칸에 토마토가 있게 되고, 하루가 지나게 되면, 앞서 말한 두 좌표로 부터 상하좌우(위 아래는 서로 토마토가 있으

         므로 접근 불가) 총 8개의 토마토가 더 익게될 것이다. 이게 하루 지나면 발생하는 일이다.

   2-3) 2-1)과 2-2)의 말을 코드적으로 설명해 보자면, 처음에 1의 좌표를 입력 받을 때, Queue에는 2개의 좌표가 들어가게

         될 것이며, Queue의 Size는 2가 될 것이다. 그럼 반복문을 2번만 실행시키면서, 익을 수 있는 토마토를 익게 만드는

         것이다. 그렇게되면, 첫 번째 반복문에서 Q.pop()의 연산을 통하면 저 두 좌표중 먼저 들어간 좌표가 나오게 될 것이

         고 상하좌우위아래로 탐색을 하면서 익지 않은 토마토들을 익게 만들 것이다. 모두 익게 만들었다면, 그 다음 반복문

         이 실행될 것이고, Q.pop()의 연산을 통해 두 좌표중 그 이후에 들어간 좌표가 나오게 될 것이다. 이 좌표 또한

         상하좌우위아래로 탐색을 하면서 익지 않은 토마토들을 익게 만들 것이다. 이렇게 반복문 2번이 끝나고 난 후에

         날짜를++ 시켜주면, 이제서야 하루 동안 익은 토마토들에 대한 계산을 할 수 있게 된다.

   2-4) 위에서 말한 것처럼, 익지 않은 토마토들이 익은 토마토에 의해서 계속해서 Queue에 push될 것이며 같은 방식으로

         날짜를 Count해주면 총 몇일이 걸리는지 쉽게 구할 수 있을 것이다.

3. 위에서 말하는 방법처럼 날짜를 구하되, 생각해야 될 부분이 하나 있다. 만약에 토마토가 다 익어서 더이상 push할 토마토

   가 없거나, 혹은, 토마토가 없는 -1 이 있는 지점 때문에 익지 않은 토마토가 있음에도 그 익지 않은 토마토에 접근할 수 

   없어서 push가 되지 않거나, 이 두 가지 경우에 대해서 생각을 해줘야 한다.

   3-1) 3)의 문제는, Queue의 Size만큼 반복문을 실행시킨 후, 날짜를++ 해주기 전에, 조건문을 통해 확인할 수 있다.

         Queue의 Size가 0인데, 익지 않은 토마토가 있는지 없는지 판단해주는 조건문만 걸어준다면 쉽게 판단할 수 있다.

   3-2) 주의해야 할 점은 날짜를 ++해주기 전에, 위의 조건문을 달아줘야 한다는 것이다.

         예를 들어서, 구현을 잘해서 모든 토마토들이 잘 익었고, 더 이상 익을 토마토가 없다고 가정해보자. 이런 경우에는

         당연히 더 이상 익을 토마토가 없으므로 모든 반복문이 끝난 후에도 Queue에 push되는 값이 없을 것이고, 

         이 경우에는, 토마토를 익게 만드는 과정이 없었기 때문에 날짜에 포함되면 안되기 때문이다. 날짜를 ++시킨 후

         최종적으로 확인을 하게 된다면, 날짜가 하루 더 증가되서 나오는 것을 확인할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int M, N, H, Empty_Space, Answer = 0;
int MAP[MAX][MAX][MAX];
bool Visit[MAX][MAX][MAX];
bool Tomato_State;
 
int dx[] = { 0, 0, 1, -1, 0, 0 };
int dy[] = { 1, -1, 0, 0, 0, 0 };
int df[] = { 0, 0, 0, 0, 1, -1 };
 
vector<pair<pair<int, int>, int >> Ripen_Tomato;
queue<pair<pair<int, int>, int>> Q;
 
void Input()
{
    Tomato_State = true;
    cin >> M >> N >> H;
    for (int k = 0; k < H; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                cin >> MAP[i][j][k];        // x, y, 높이
                if (MAP[i][j][k] == 0) Tomato_State = false;
                if (MAP[i][j][k] == 1) Q.push(make_pair(make_pair(i, j), k));
            }
        }
    }
}
 
bool Check_Tomato_State()
{
    for (int k = 0; k < H; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (MAP[i][j][k] == 0) return false;
            }
        }
    }
    return true;
}
 
void BFS()
{
    while (Q.empty() == 0)
    {
        int Qs = Q.size();
 
        for (int Q_s = 0; Q_s < Qs; Q_s++)
        {
            int x = Q.front().first.first;
            int y = Q.front().first.second;
            int f = Q.front().second;
            Q.pop();
 
            for (int i = 0; i < 6; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nf = f + df[i];
 
                if (nx >= 0 && ny >= 0 && nf >= 0 && nx < N && ny < M && nf < H)
                {
                    if (MAP[nx][ny][nf] == 0)
                    {
                        MAP[nx][ny][nf] = 1;
                        Q.push(make_pair(make_pair(nx, ny), nf));
                    }
                }
            }
            if (Q.size() == 0 && Check_Tomato_State() == true)
            {
                cout << Answer << endl;
                return;
            }
            else if (Q.size() == 0 && Check_Tomato_State() == false)
            {
                cout << -1 << endl;
                return;
            }
        }
        Answer++;
    }
}
 
void Solution()
{
    if (Tomato_State == true)
    {
        cout << 0 << endl;
        return;
    }
 
    BFS();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}