문제

문제 링크 : https://www.acmicpc.net/problem/7569

풀이

BFS를 이용해서 풀었다.

처음에 입력을 받으면서 값이 1인 칸의 좌표들을 큐에 넣어주고 bfs 함수에서 순서대로 빼줬다. 그 뒤에 인접한 칸의 값이 0인 경우에 그 칸들의 좌표를 다시 큐에 넣어줬고, 더 이상 0인 칸이 나오지 않을 때까지 반복해줬다.

bfs 함수가 끝난 뒤에 tomato 리스트를 돌면서 0인 칸이 남아 있는지 검사해줬다. 만약에 0인 칸이 남아 있다면 result 값을 -1로 바꿔주었다.

이후에 result 값을 출력하면 끝나게 된다.

from sys import stdin
from collections import deque

m,n,h = map(int,stdin.readline().split())

tomato = [[[] for j in range(n)] for i in range(h)]
queue = deque()


for i in range(h):
    for j in range(n):
        tomato[i][j] = list(map(int,stdin.readline().split()))
        for k in range(len(tomato[i][j])):
            if tomato[i][j][k] == 1:
                queue.append((i,j,k,0))

visited = [[[0 for i in range(m)] for j in range(n)] for k in range(h)]
result = 0

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

def bfs(x,y,z,day):
    global result
    global queue
    visited[x][y][z] = 1
    while queue:
        x,y,z,day = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx < 0 or ny < 0 or nz < 0 or nx >= h or ny >= n or nz >= m:
                continue
            if tomato[nx][ny][nz] != 0:
                continue
            if visited[nx][ny][nz] == 1:
                continue
            visited[nx][ny][nz] = 1
            tomato[nx][ny][nz] = 1
            result = max(result, day + 1)
            queue.append((nx,ny,nz,day + 1))

if len(queue) != 0:
    x,y,z,day = queue[0]
    bfs(x,y,z,day)

for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 0:
                result = -1
                break
        if result == -1:
            break
    if result == -1:
        break

print(result)