백준 7569번(토마토) C++ 풀이

#include <iostream>
#include <queue>
using namespace std;

int N, M, H;
int fruit[101][101][101]; // H M N
int visited[101][101][101];
int direci[6] = {0, 0, 0, 0, -1, 1};
int direcj[6] = {0, -1, 0, 1, 0, 0};
int direcy[6] = {1, 0, -1, 0, 0, 0};
queue<pair<pair<int, int>, int>> q;
void bfs()
{

    while (!q.empty())
    {

        int fronti = q.front().first.first;
        int frontj = q.front().first.second;
        int fronty = q.front().second;
        q.pop();
        for (int i = 0; i < 6; i++)
        {
            int pi = fronti + direci[i];
            int pj = frontj + direcj[i];
            int py = fronty + direcy[i];
            if (pi >= 0 && pi < H && pj >= 0 && pj < M && py >= 0 && py < N)
            {
                if (fruit[pi][pj][py] == 0)
                {
                    fruit[pi][pj][py] = fruit[fronti][frontj][fronty] + 1;
                    q.push({{pi, pj}, py});
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> H;

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int y = 0; y < N; y++)
            {
                cin >> fruit[i][j][y];
            }
        }
    }

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int y = 0; y < N; y++)
            {
                if (fruit[i][j][y] == 1)
                {
                    q.push({{i, j}, y});
                }
            }
        }
    }
    int d = 0;
    bfs();
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int y = 0; y < N; y++)
            {
                if (fruit[i][j][y] == 0)
                {
                    cout << -1;
                    return 0;
                }
                else
                {
                    if (fruit[i][j][y] > d)
                    {
                        d = fruit[i][j][y];
                    }
                }
            }
        }
    }
    cout << d - 1;
}

노가다에 가까운 BFS 문제였다...

int visited[101][101][101];
int direci[6] = {0, 0, 0, 0, -1, 1};
int direcj[6] = {0, -1, 0, 1, 0, 0};
int direcy[6] = {1, 0, -1, 0, 0, 0};

먼저, 기본적인 BFS 문제 개념에, 3차원 박스에서의 토마토가 익어가는 과정을 생각해서, 3차원 배열과 그리고 6개의 방향으로 향할 수 있게 6개의 direc을 만들어주었다.

                if (fruit[pi][pj][py] == 0)
                {
                    fruit[pi][pj][py] = fruit[fronti][frontj][fronty] + 1;
                    q.push({{pi, pj}, py});
                }

그리고 흔히 접할 수 있는 BFS 문제와 달리, visited가 아닌 fruit를 증가시키는 방향으로 설정했다. 처음에는 visited를 증가시켜 이 visited의 최댓값을 구하는 식으로 해결하려 하였으나..

10 1 1
1 0 0 0 0 0 0 0 0 1

대충 이런식으로, 양방향에서 토마토가 익어가는 과정에서 계산의 오류가 발생할 수 밖에 없었다. 그렇기때문에, visited를 이용하는 것이 아닌, 모든 배열에서 bfs를 실행하는 방식으로 문제를 해결하였다.