
🔗 문제 링크
https://www.acmicpc.net/problem/7569
💻 코드
import sys
input = sys.stdin.readline
from collections import deque
# 최소일수: BFS
dq = deque()
m,n,h = map(int,input().split())
tomato = []
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
for i in range(h):
tomato.append([])
for _ in range(n):
tomato[i].append(list(map(int,input().split())))
def contains_zero(arr):
for sub_arr in arr:
for inner_arr in sub_arr:
if 0 in inner_arr:
return 1
return 0
def is_valid(z,x,y):
if 0 <= z < h:
if 0 <= x < n:
if 0 <= y < m:
return 1
return 0
def bfs():
dir = [
[-1,0,0], [1,0,0],
[0,1,0], [0,0,-1], [0,-1,0], [0,0,1]
]
while dq:
ch, cx,cy,day = dq.popleft()
for i,j,k in dir:
nh = ch+i
nx,ny = cx+j, cy+k
if is_valid(nh,nx,ny):
if not visited[nh][nx][ny]:
if tomato[nh][nx][ny] == 0:
tomato[nh][nx][ny] = 1
visited[nh][nx][ny] = 1
dq.append((nh,nx,ny,day+1))
return day
if not contains_zero(tomato):
print(0)
exit(0)
for i in range(h):
for j in range(n):
for k in range(m):
if tomato[i][j][k] == 1:
dq.append((i,j,k,0))
visited[i][j][k] = 0
if not dq:
print(-1)
exit(0)
result = bfs()
if contains_zero(tomato):
print(-1)
else:
print(result)
🤷♂ 풀이
처음에 계속 틀렸는데 이유가 맨처음 좌표가 1이되는 시작점부터 시작했기 때문이다.
동시에 시작해야하므로, 다중 시작점 BFS로 접근해야한다.
UnboundLocalError
: bfs함수를 실행할 때, tomato가 1이아닌 곳만 있어서 deque가 비어있을 수 있다. 이런 경우에는 토마토가 익을 수 없기에 -1을 출력해줘야한다.다중시작점을 제외하고는 일반 BFS와 동일하게 풀면되는데, 토마토상자가 높이까지 존재하다보니까 3차원 배열을 사용해서 푸는 것이 적절하다.