7569 토마토

문제 링크

• 풀이

이전 토마토 문제와 마찬가지로 BFS 이용해 풀 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct tmt
{
    int r, c, h, t;
};

int M, N, H, Z;
int box[102][102][102];
int dr[] = { -1, 1, 0, 0, 0, 0 };
int dc[] = { 0, 0, -1, 1, 0, 0 };
int dh[] = { 0, 0, 0, 0, -1, 1, };

int bfs(queue<tmt>& q)
{
    int t = 0;

    while (!q.empty())
    {
        int r = q.front().r;
        int c = q.front().c;
        int h = q.front().h;
        t = q.front().t;
        q.pop();

        for (int d = 0; d < 6; d++)
        {
            int nr = r + dr[d];
            int nc = c + dc[d];
            int nh = h + dh[d];

            if (box[nr][nc][nh])
                continue;

            box[nr][nc][nh] = 1;
            Z -= 1;
            q.push({ nr, nc, nh, t + 1 });
        }
    }

    if (Z)
        return -1;

    return t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<tmt> q;

    memset(box, -1, sizeof(box));

    cin >> M >> N >> H;

    for (int h = 1; h <= H; h++)
    {
        for (int r = 1; r <= N; r++)
        {
            for (int c = 1; c <= M; c++)
            {
                cin >> box[r][c][h];
                if (box[r][c][h] == 1)
                {
                    q.push({ r, c, h, 0 });
                }
                else if (box[r][c][h] == 0)
                {
                    Z += 1;
                }
            }
        }
    }

    cout << bfs(q) << "\n";

    return 0;
}

• 더 빠른 풀이를 위해 fread를 이용할 수 있다.

#include <cstdio>

char b[100][100][100];
char buf[1<<15];
int idx = 1<<15;
struct pos { char z, y, x; int c; };

inline char read()
{
    if (idx == 1<<15)
    {
        fread(buf, 1, 1<<15, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt()
{
    int sum = 0;
    bool fl = false;
    char nw = read();
    
    while (nw == ' ' || nw == '\n' || nw == '\r') nw = read();
    if (nw == '-') fl = true, nw = read();
    while (nw >= '0' && nw <= '9')
    {
        sum = sum*10 + nw-48;
        nw = read();
    }
    
    return fl ? -sum : sum;
}
int main()
{
    int m, n, h;
    pos q[1000000];
    int fnt = 0, bck = 0;
    int zero = 0;

    m = readInt();
    n = readInt();
    h = readInt();
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < m; ++k) {
                b[i][j][k] = readInt();
                if (b[i][j][k] == 1) {
                    q[bck++] = { i,j,k,0 };
                    b[i][j][k] = 2;
                }
                else if (!b[i][j][k]) zero++;
            }
        }
    }

    while (fnt != bck) {
        int z = q[fnt].z;
        int y = q[fnt].y;
        int x = q[fnt].x;
        int c = q[fnt].c + 1;

        fnt++;

        if (z && b[z - 1][y][x] == 0) zero--, q[bck++] = { z - 1,y,x,c }, b[z - 1][y][x] = 2;
        if (y && b[z][y - 1][x] == 0) zero--, q[bck++] = { z,y - 1,x,c }, b[z][y - 1][x] = 2;
        if (x && b[z][y][x - 1] == 0) zero--, q[bck++] = { z,y,x - 1,c }, b[z][y][x - 1] = 2;
        if (z < h - 1 && b[z + 1][y][x] == 0) q[bck++] = { z + 1,y,x,c }, b[z + 1][y][x] = 2, zero--;
        if (y < n - 1 && b[z][y + 1][x] == 0) q[bck++] = { z,y + 1,x,c }, b[z][y + 1][x] = 2, zero--;
        if (x < m - 1 && b[z][y][x + 1] == 0) q[bck++] = { z,y,x + 1,c }, b[z][y][x + 1] = 2, zero--;
    }

    printf("%d", zero > 0 ? -1 : q[--bck].c);

    return 0;
}