[BFS 파이썬] 백준 7576. 토마토

 

 

문제

토마토 익으려면 얼마나 걸려?

 

주의 :

pypy로 해야지만 시간 초과가 안떴다.

 

난이도 : 

다시보니, 훨 이해가 잘간다!

 

 

import sys
from collections import deque
sys.stdin = open('./BFS/input2.txt','rt')
input = sys.stdin.readline

m,n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n) ]
queue = deque([])

# 1 한 놈 queue에 넣고 시작
for i in range(n):
    for j in range(m):
        if g[i][j] == 1:
            queue.append([i,j])
            
# print(queue)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def BFS():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            a = x+dx[i]
            b = y+dy[i]

            if 0<=a<n and 0<=b<m and g[a][b] == 0:
                # 안익었으면, 익혀!
                queue.append([a,b])
                g[a][b] = g[x][y] + 1

BFS()
res = 0
print(g)
for i in g:     # 행마다 꺼내고
    for j in i: # 행의 요소마다 꺼내
        if j == 0: # 안 익은 게 있으면 -1 출력하고 끝내
            print(-1)
            sys.exit(0)
        
        res = max(res, max(i)) 
        # 행의 가장 큰 값 => 가장 나중에 익은 토마토
print(res-1)

 

* 참고

https://jiwon-coding.tistory.com/97