문제
토마토 익으려면 얼마나 걸려?
주의 :
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)
* 참고
'⚡️algorithm' 카테고리의 다른 글
[완전탐색, 파이썬] 백준 1107. 리모컨 (0) | 2022.04.29 |
---|---|
[완전탐색, 파이썬] 백준 1476. 날짜계산 (0) | 2022.04.29 |
[DFS, 파이썬] 백준 4963. 섬의 개수 (0) | 2022.04.29 |
[DFS] 백준 10265. MT - 틀림 (0) | 2022.04.28 |
[DFS, 파이썬] 백준 2468. 안전영역 (0) | 2022.04.27 |