[백준] [Python] 7569번 토마토(3차원) - BFS

www.acmicpc.net/problem/7569

7569번: 토마토

 

 

Python

import sys
from collections import deque
m, n, h = map(int, sys.stdin.readline().split())
visit = [[[0]*m for _ in range(n)] for _ in range(h)]
tomato = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]

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


q = deque()

#left = m*n*h
left = 0
for a in range(h):
    for b in range(n):
        for c in range(m):
            if tomato[a][b][c] == 1:
                q.append((a, b, c))
            elif tomato[a][b][c] == 0:
                left += 1

if left==0:
    print(0)
    sys.exit(0)
    

cnt = 0
while len(q) != 0:
    #print(q)
    z,y,x = q.popleft()

    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        #print(nz,ny,nx, q)
        if 0<=nx<m and 0<=ny<n and 0<=nz<h:
            if visit[nz][ny][nx] == 0 and tomato[nz][ny][nx] == 0:
                visit[nz][ny][nx] = visit[z][y][x] + 1
                q.append((nz, ny, nx))
                left-=1
                cnt = max(cnt, visit[nz][ny][nx])
                
                
if cnt==0 or left>0: print(-1)
else: print(cnt)

 

 

짧은 풀이

• !! 분명 맞게 적었는데 시간초과가 뜬다면 'PyPy3' 언어로 설정하여 돌려보자.
  • Python3는 간단한 코드에서, PyPy3는 복잡한 코드(반복, 재귀 등)에서 효율적이다.
  • 삼성 코테는 PyPy를 이용한다고 한다.
• left 변수는 익어야하는 토마토의 개수를 담는다. 하나도 없다면 모두 다 익은 상태이므로 0을 출력하도록 한다.
• 익은 토마토는 무조건 큐에 담아서 반복문을 돌려본다.
• 익게 된 토마토를 찾으면 익어야 하는 토마토의 개수를 하나씩 차감하고, 현재까지 걸린 시간 중 가장 오래된 시간을 cnt 변수에 담는다.
• 마지막에 단 하루도 필요하지 않다거나, 아직 익지 않은 토마토가 남아있다면 -1을 출력한다.