7569번

7569번 -  토마토

3차원 BFS로 풀면 된다. 단 토마토가 익었더라고 하더라도, 거리가 짧으면 다시 큐에 넣어야 한다.

그리고 다 돌리고 나서 익지 않은 토마토가 있다면 -1을 출력해야 하고,

그렇지 않다면 dist 배열에서 가장 큰 값을 출력해야 한다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
 
typedef struct {
    int a;
    int b;
    int c;
}tomato;
using namespace std;
int dx[6] = { 0,0,1,-1,0,0 };
int dy[6] = { 1,-1,0,0,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
int map[101][101][101];
int dist[101][101][101];
int n, m, h;
vector<tomato> v;
void bfs(tomato T)
{
    queue<tomato> q;
    q.push(T);
    dist[T.a][T.b][T.c] = 0;
 
    while (!q.empty())
    {
        int x = q.front().b;
        int y = q.front().c;
        int z = q.front().a;
        q.pop();
 
        for (int d = 0; d < 6; d++)
        {
            tomato tmp;
            int nx = x + dx[d];
            int ny = y + dy[d];
            int nz = z + dz[d];
            tmp.b = nx, tmp.c = ny, tmp.a = nz;
 
            if (nx >= 0 && ny >= 0 && nz >= 0 && nx < m && ny < n && nz < h && map[nz][nx][ny] != -1)
            {
                if (map[nz][nx][ny]==0)
                {
                    map[nz][nx][ny] = 1;
                    dist[nz][nx][ny] = dist[z][x][y] + 1;
                    q.push(tmp);
                }
                else
                {
                    if (dist[nz][nx][ny] > dist[z][x][y] + 1)
                    {
                        dist[nz][nx][ny] = dist[z][x][y] + 1;
                        q.push(tmp);
                    }
                    
                }
            }
        }
    }
 
    
}
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> h;
 
    for (int t = 0; t < h; t++)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[t][i][j];
                if (map[t][i][j] == 1)
                {
                    tomato tmp;
                    tmp.a = t, tmp.b = i, tmp.c = j;
                    v.push_back(tmp);
                }
            }
        }
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        bfs(v[i]);
    }
 
    int ans = 0;
    
    for (int t = 0; t < h; t++)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[t][i][j] != -1)
                {
                    if (map[t][i][j] == 0)
                    {
                        cout << "-1\n";
                        return 0;
                    }
                    else
                    {
                        if (dist[t][i][j] > ans)
                        {
                            ans = dist[t][i][j];
                        }
                    }
 
                }
            }
        }
    }
 
    cout << ans << "\n";
    return 0;
}