백준 7569 / 토마토

BFS 연습문제

* 절대 2차원배열로 퉁치면 안되는 문제다!

처음엔 2차원배열로 받아서 위/아래로 갈경우 N만큼 증가/감소시켜서 풀어보려고 했으나

그렇게풀면

첫번째 박스의 마지막 행이 두번째 박스의 첫째 행과 연결된다는 큰 오류가 있음을 깨달았다.

그래서 3차원배열로 해결했다.

코드

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
 
using namespace std;
 
 
int n, m, h;
int map[101][101][101];
int d[101][101][101];
bool check[101][101][101];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int dz[] = { 1,-1 };
queue<tuple<int,int,int>>q;
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> m >> n >> h;
 
    bool istherezero = true;
 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> map[j][k][i];
                if (map[j][k][i]== 1) {
                    q.push(make_tuple(j,k,i));
                    check[j][k][i] = true;
 
                }
                if (map[j][k][i] == 0) {
                    istherezero = false;
                }
 
            }
        }
    }
 
    if (istherezero == true) {
        cout << 0;
        return 0;
    }
 
    while (!q.empty()) {
    
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (map[nx][ny][z] == 0 && check[nx][ny][z] == false) {
                    map[nx][ny][z] = 1;
                    check[nx][ny][z] = true;
                    d[nx][ny][z] = d[x][y][z] + 1;
                    q.push(make_tuple(nx, ny,z));
                }
            }
        }
 
        for (int i = 0; i < 2; i++) {
            int nz = z + dz[i];
            if (nz >= 0 && nz < h) {
                if (map[x][y][nz] == 0 && check[x][y][nz] == false) {
                    map[x][y][nz] = 1;
                    check[x][y][nz] = true;
                    d[x][y][nz] = d[x][y][z] + 1;
                    q.push(make_tuple(x, y,nz));
                }
            }
        }
    }
 
    int ans = -20000000;
    bool allgood = true;
    
    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = max(ans, d[i][j][k]);
                if (map[i][j][k] == 0) {
                    allgood = false;
                }
                
            }
        }
    }
 
 
    if (allgood == false) {
        cout << -1;
    }
    else
        cout << ans;
 
}