chldkato

백준 7569 토마토 (파이썬) 본문

백준

백준 7569 토마토 (파이썬)

chldkato 2020. 2. 16. 21:00

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마

www.acmicpc.net

z축을 추가하면 풀리는 문제

 

주어진 입력에서 모든 토마토를 큐에 넣은 후 bfs를 수행하여 걸리는 시간을 출력

from collections import deque
import sys

dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

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 0 <= nx < k and 0 <= ny < n and 0 <= nz < m:
                if a[nx][ny][nz] == 0 and c[nx][ny][nz] == 0:
                    q.append([nx, ny, nz])
                    a[nx][ny][nz] = 1
                    c[nx][ny][nz] = c[x][y][z] + 1

m, n, k = map(int, input().split())
a = [[list(map(int, input().split())) for _ in range(n)] for _ in range(k)]
c = [[[0]*m for _ in range(n)] for _ in range(k)]
q = deque()

for i in range(k):
    for j in range(n):
        for l in range(m):
            if a[i][j][l] == 1 and c[i][j][l] == 0:
                q.append([i, j, l])
                c[i][j][l] = 1

bfs()
for i in a:
    for j in i:
        if 0 in j:
            print(-1)
            sys.exit()
ans = 0
for i in c:
    for j in i:
        list_max = max(j)
        ans = max(ans, list_max)
print(ans-1)

Comments