[baekjoon] 백준 7569번 : 토마토 (by python) bfs 너비우선 탐색

https://www.acmicpc.net/problem/7569

7569번: 토마토

 

정답 code

#토마토
from collections import deque
import sys
input = sys.stdin.readline
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]
queue = deque()

m , n , h = map(int,input().split())
box = []
for i in range(h):
    tmp = []
    for j in range(n):
        tmp.append(list(map(int,input().split())))
        for k in range(m):
            if tmp[j][k] == 1:
                queue.append([i,j,k])
    box.append(tmp)

while queue:
    x,y,z = queue.popleft()

    for i in range(6):
        a = x + dx[i]
        b = y + dy[i]
        c = z + dz[i]
        if 0<= a < h and 0<= b < n and 0<= c < m and box[a][b][c]==0:
            queue.append([a,b,c])
            box[a][b][c] = box[x][y][z]+ 1

day = 0
for i in box:
    for j in i:
        for k in j:
            if k == 0:
                print(-1)
                exit(0)
        day = max(day,max(j))

print(day-1)

 

solution

처음엔 이중리스트를 통해 구현했다. n이 3이고 h가 2이면 [[],[],[],[],[],[]] 이런식으로 구현하여 n*h를 통해 원하는 위치를 찾았는데 너무 복잡하고 의미가 없었다.

그래서 다시 3중 리스트를 통해 구현했다.

 

바로 box [] 에 넣는것보다 tmp에 추가해 1이 있으면 queue에 추가해준다.

그후 n 만큼 추가되면 통채로 box에 넣어 한개의 층을 만들어준다.

 

이후에는 bfs가 실행되는데 queue에 익은토마토의 좌표가 들어있음으로 popleft를 통해 꺼내고

dx,dy,dz를 이용해 상하좌우에 있는 토마토가 익지 않았다면 +1한 값을 넣어준다.

 

3중 for문을 통해 익지않은 토마토가 아직 있다면 -1을 출력해주고

아니라면 box속의 최대값을 찾아준다음 익은토마토가 1부터 시작했음으로 -1을 한값이 걸린 날짜가 된다.