[백준-파이썬] 7569: 토마토

백준 7569번 문제~

😍 코드와 설명

BFS로 풀었다!

import sys
from collections import deque

#앞뒤좌우상하를 봐야 하므로
dx=[-1,0,1,0,0,0] 
dy=[0,1,0,-1,0,0]
dz=[0,0,0,0,1,-1]

#입력받기
m,n,h=map(int,input().split())
tomato_zone=list(list(list(map(int,input().split())) for _ in range(n)) for _ in range(h))

#deque만들기
Q=deque()
days=[[[0]*m for _ in range(n)] for _ in range(h)]

#쭉 보면서 익은 토마토를 발견하면 모두 deque에 넣는다.
for x in range(h):
    for y in range(n):
        for z in range(m):
            if tomato_zone[x][y][z]==1:
                Q.append((x,y,z))

#deque에서 하나씩 빼서 보면서
while Q:
    tmp=Q.popleft()
    for i in range(6): #상하좌우앞뒤를 보면서
        xx=tmp[0]+dx[i]
        yy=tmp[1]+dy[i]
        zz=tmp[2]+dz[i]

        #범위에 해당하고, 안 익은 토마토이면 
        if 0<=xx<h and 0<=yy<n and 0<=zz<m and tomato_zone[xx][yy][zz]==0:
            tomato_zone[xx][yy][zz]=1  #토마토를 익힌다. 
            #그 위치가 익는 데 며칠 걸렸는지를 days 리스트에 저장
            days[xx][yy][zz]=days[tmp[0]][tmp[1]][tmp[2]]+1 
            Q.append((xx,yy,zz))


def all_tomato_done(tomato_zone):
    '''모든 토마토가 익었는지 체크하는 함수'''
    for x in range(h):
        for y in range(n):
            for z in range(m):
                if tomato_zone[x][y][z]==0:
                    return -1
    return 0

if all_tomato_done(tomato_zone)==-1:
    print(-1)
else:
    ans=0 #days에서 토마토가 익는 데 최대로 걸린 일수가 며칠인지 찾아서 정답을 출력
    for x in range(h):
        for y in range(n):
            for z in range(m):
                if days[x][y][z]>ans:
                    ans=days[x][y][z]
    print(ans)

🤗 배운 점

3차원 리스트 자체를 많이 다뤄보지 않았고, 3차원 리스트로 BFS 문제를 푸는 것은 처음이었다! 그래도 2차원 리스트를 활용한 BFS 문제 풀던 대로 하니까 풀 수 있었다!

위, 아래, 좌, 우, 앞, 뒤라서 6가지 경우를 체크해봐야 했는데.. 나는 range(4)로 두고 "왜 안되지?'고민하고 있었다. 친구가 보고 4가 아니라 6으로 해야 한다고 알려줘서 그것을 수정하니까 되었다!! ㅋㅋ 자기가 볼 때는 문제가 잘 안보이는데, 다른 사람이 봐주면 금방 찾을 때가 있다..ㅎㅎ 서로 도우면서 하면 좋다는 걸 다시 한번 느꼈다!

아 그리고 파이썬으로 하니까 시간 초과가 나왔다.. pypy로 하니까 통과할 수 있었다...ㅎㅎ
다른 분들이 파이썬으로 하신 코드를 보는 것도 재미있었다.