[백준/파이썬] 7569번 토마토 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 7569번 토마토
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

3차원 상자에서 익은 토마토가 인접 칸으로 퍼질 때, 모든 토마토가 익는 최소 일수를 구하는 문제입니다. 불가능하면 -1을 출력합니다.

코드

import sys;read=sys.stdin.readline
from collections import deque
m,n,h=map(int,read().split())
# tomatos[h][n][m]
tomatos=[[list(map(int,read().split()))for j in range(n)]for i in range(h)]
Q,d=deque([]),((0,0,-1),(0,0,1),(0,-1,0),(0,1,0),(-1,0,0),(1,0,0))
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomatos[i][j][k]==1:Q.append((i,j,k,tomatos[i][j][k]))
while Q:
    i,j,k,c=Q.popleft()
    for move in d:
        mi,mj,mk=i+move[0],j+move[1],k+move[2]
        if 0<=mi<h and 0<=mj<n and 0<=mk<m and tomatos[mi][mj][mk]==0:
            tomatos[mi][mj][mk]=c+1
            Q.append((mi,mj,mk,c+1))
f=False
for floor in tomatos:
    for row in floor:
        for tomato in row:
            if tomato==0:
                f=True
                break
        if f:break
    if f:break
print(-1 if f else c-1)

설명

모든 익은 토마토를 큐에 넣고 동시에 BFS를 시작해 각 칸에 익는 날짜를 기록합니다. 탐색 후 0이 남으면 -1, 아니면 마지막 날짜 기준 일수를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---