BOJ 7569 · 토마토

알고리즘 분류 : BFS  

7576번 토마토 문제가 약간 변형된 문제다. 토마토 상자가 2차원에서 3차원으로 업그레이드되었다. 원래 문제는 범위가 1000 X 1000이었는데, 이번 문제는 100 X 100 X 100이다. 최대 10^6이므로 완전 탐색이 가능하다. 3차원 배열을 통한 BFS를 돌리면 된다.

7576번 문제에 대한 해설과 코드는 이곳에서 참조.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct tomato {
    int x, y, z;
};

int m, n, h, ans;
int a[101][101][101];
const int dx[] = {-1, 1, 0, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};
queue<tomato> q;

void bfs() {
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = q.front().z;
        q.pop();
        for (int i=0; i<6; i++) {
            int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= n || nz < 0 || nz >= m) continue;
            if (a[nx][ny][nz]) continue;    // Ripened(1 or above), empty(-1)
            a[nx][ny][nz] = a[x][y][z] + 1; // Day count
            q.push({nx, ny, nz});
        }
    }
}

int main() {
    scanf("%d %d %d", &m, &n, &h);
    for (int i=0; i<h; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<m; k++) {
                scanf("%d", &a[i][j][k]);
                if (a[i][j][k] == 1) {
                    // Ripened(1), Not ripened(0), Empty(-1)
                    // Push {i,j,k} to queue, if 1.
                    q.push({i, j, k});
                }
            }
        }
    }
    bfs();
    for (int i=0; i<h; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<m; k++) {
                // Not all tomato ripened.
                if (a[i][j][k] == 0) {
                    printf("-1\n");
                    return 0;
                }
                // Max value is answer.
                if (ans < a[i][j][k]) ans = a[i][j][k];
            }
        }
    }
    printf("%d\n", ans-1);
    return 0;
}

---

Python 3 소스코드

import sys
from collections import deque

dx = (-1, 1, 0, 0, 0, 0)
dy = (0, 0, -1, 1, 0, 0)
dz = (0, 0, 0, 0, -1, 1)
m, n, h = map(int, sys.stdin.readline().split())
a = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if a[i][j][k] == 1:
                q.append((i, j, k))

def bfs():
    while q:
        x, y, z = q.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m:
                continue
            if a[nx][ny][nz]:
                continue
            a[nx][ny][nz] = a[x][y][z] + 1
            q.append((nx, ny, nz))

def solve():
    bfs()
    ans = 0
    for i in range(h):
        for j in range(n):
            if 0 in a[i][j]:
                return -1
            ans = max(ans, max(a[i][j]))
    return ans-1

print(solve())

---

참고

• 백준 온라인 저지 : BOJ 7569
• 토마토 (7576번)