[백준/C++] 7569번 토마토

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

7569번: 토마토

bfs문제인데, 3차원 bfs문제이다. 즉 상하좌우 + 위 아래 방향도 탐색해주면 된다.

큐에는 기존에 x,y좌표만 넣었지만, 3차원이므로 x,y좌표와 몇 층인지 해당하는 정보를 넣어주면 된다.

dist배열엔 토마토가 익는 시간을 저장해주면 된다. 만약 이 dist배열에 들어있는 값이 0보다 크다면, 이미 방문했던 (=토마토가 익어버린) 곳이라는 뜻이므로 굳이 탐색하지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int tomato[101][101][101];
int n,m,h,ans;
int dz[6] = { 0,0,0 ,0,-1,1 };
int dx[6] = {0,0 ,1,-1,0,0};
int dy[6] = {-1,1,0,0,0,0 };
int dist[101][101][101];

// x,y좌표 + 층
queue<pair<pair<int,int>,int>> q;

void bfs(){
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int floor = q.front().second;

        q.pop();
        for (int i = 0; i < 6; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nz = floor + dz[i];

            if (nx < 0 || nx >= m || ny < 0 || ny >= n|| nz < 0 || nz >= h) continue;
            if (dist[nx][ny][nz] >= 0) continue; // 이미 방문한 곳이면 continue;
            dist[nx][ny][nz] = dist[x][y][floor] + 1;
            q.push({{ nx,ny },nz});
        }
    }
    for(int k=0;k<h;k++) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j][k] == -1) {
                    cout << -1;
                    return;
                }
                ans = max(ans, dist[i][j][k]);
            }
        }
    }
    cout << ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> h;
    for(int k=0;k<h;k++) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> tomato[i][j][k];

                if (tomato[i][j][k] == 1) {
                    q.push({ {i,j},k });
                }
                if (tomato[i][j][k] == 0)
                    // 익지 않은 토마토면 초기화
                    dist[i][j][k] = -1;
            }
        }
    }
    bfs();
}