[7569번] 토마토

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 3차원 BFS

BFS중에서 3차원 배열에 대한 BFS를 구현해라는 문제이다.

문제는 어렵지 않지만 귀찮은 요소가 꽤나 존재한다.

1. 우선 입력을 받을 때 '0'인 값 즉, 토마토가 익어야 하는 인덱스를 만나면 tomato를 +1해준다.

2. BFS를 돌리는데 현재 인덱스가 0인 값이면 tmpTomato를 +1 해준다(혹은 tomato를 -1해줘서 맞추어 나가도 된다.)

3. 범위를 벗어나거나, 가려는 위치가 1, -1이면 continue를 시켜주고 0인 부분에 대해서만 큐에 push해준다.

4. 큐에서 day를 계속 구해주고, 최종적으로 BFS가 끝났을 때 tmpTomato와 tomato가 같으면 모든 토마토가 익은 것이고,

day를 출력하면 된다. 그게 아니라면 -1을 출력한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
 
using namespace std;
 
typedef pair<pair<int, int>, pair<int, int> > pii;
 
int arr[102][102][102];
bool visit[102][102][102];
 
int dz[6] = { 1, 0, 0, 0, 0, -1, };
int dy[6] = { 0, 1, 0, -1, 0, 0 };
int dx[6] = { 0, 0, 1, 0, -1, 0 };
 
int main()
{
    int m, n, h, tomato = 0;
    scanf("%d %d %d", &n, &m, &h);
 
    for (int i = 0; i < h; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < n; k++)
            {
                scanf("%d", &arr[i][j][k]);
                if (arr[i][j][k] == 0)
                    tomato++;
            }
 
    // 1 : 익음, 0 : 안익음, -1 : 없음
    int day = 0;
    queue<pii> q;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < n; k++)
                if (arr[i][j][k] == 1)
                    q.push({ { 0,i },{ j,k } });
 
    int tmpTomato = 0;
    while (!q.empty())
    {
        int tday = q.front().first.first;
        int z = q.front().first.second;
        int y = q.front().second.first;
        int x = q.front().second.second;
 
        q.pop();
 
        if (visit[z][y][x])
            continue;
 
        day = max(day, tday);
 
        if (arr[z][y][x] == 0)
            tmpTomato++;
 
        arr[z][y][x] = 1;
        visit[z][y][x] = true;
    
        for (int i = 0; i < 6; i++)
        {
            int dZ = dz[i] + z;
            int dY = dy[i] + y;
            int dX = dx[i] + x;
 
            // 범위를 벗어나면
            if (!(0 <= dZ && dZ < h && 0 <= dY && dY < m && 0 <= dX && dX < n))
                continue;
 
            // 해당 구역이 0이 아니면
            if (arr[dZ][dY][dX] != 0)
                continue;
 
            q.push({ {tday+1,dZ}, {dY, dX} });
        }
    }
 
    if (tmpTomato == tomato)
        printf("%d", day);
    else
        printf("-1");
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>