[백준][7569번] 토마토[cpp, c++]

백준 7569번 토마토

• BFS 문제이다.
• https://www.acmicpc.net/problem/7569

7569번: 토마토

• 풀이방법
  1) 높이가 있어서 3차원배열이라고 생각하면 된다.
  2) x,y,z가 담긴 구조체를 만들고 bfs를 돌린다.
  3) 일수를 구하는 tomato 배열만 이용해서, check배열은 필요하지 않다.

 
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef struct {
    int x, y, z;
}xyz;
queue<xyz> q;
int tomato[101][101][101];
int M, N, H;
int nx[7] = { 1,0,-1,0,0,0 };
int ny[7] = { 0,1,0,-1,0,0 };
int nz[7] = { 0,0,0,0,1,-1 };
int ans;
void bfs() {
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int z = q.front().z;
        q.pop();
        for (int i = 0; i < 6; i++) {
            int dx = x + nx[i];
            int dy = y + ny[i];
            int dz = z + nz[i];
            if (dz < 0 || dz >= H || dx >= M || dx < 0 || dy >= N || dy < 0) continue;
            if (tomato[dz][dx][dy]!=0) continue;
                q.push({ dx,dy,dz });
                tomato[dz][dx][dy] = tomato[z][x][y] + 1;
        }
    }
}
 
 
 
int main(void){
    cin >> N >> M >> H;
    int flag = 0;
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                cin >> tomato[k][i][j];
                if (tomato[k][i][j]==1) q.push({ i,j,k });
                if (tomato[k][i][j] == 0) flag = 1;
            }
        }
    }
 
    if (flag==0) { //전부 0이면
        cout << 0;
        return 0;
    }
    bfs();
 
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (tomato[k][i][j] == 0) {
                    cout << -1;
                    return 0;
                }
                else if (tomato[k][i][j] >= ans) ans = tomato[k][i][j];
            }
        }
    }
 
 
 
 
 
    cout << ans-1;
    return 0;
}