[백준] 7576번. 토마토

아이디어

• 문제가 하라는대로 했다
• 전형적인 bfs 문제
• 처음부터 익은 토마토가 없으면 바로 -1 출력
  (그냥 빈 q를 보내면r, c, day가 비어있어서 UnboundError 난다)

시간복잡도

• 익은 토마토 찾는 부분 : 이중 for 문 = O(n * m) (1,000,000)
• tomato() : while = O(n * m)
• 안익은 토마토 찾는 부분 : enumerate = O(m)

코드

from collections import deque
import sys
input = sys.stdin.readline

# 토마토 익히기
def tomato(q):
    while q:
        r, c, day = q.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            # 이동가능한 범위이고 익지 않은 토마토라면
            if 0 <= nr < n and 0 <= nc < m and box[nr][nc] == 0:
                q.append((nr, nc, day + 1))
                box[nr][nc] = 1

    return day


m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
q = deque([])


# 익은 토마토(1) 찾기
for r in range(n):
    for c in range(m):
        if box[r][c] == 1:
            q.append((r, c, 0))

# q가 안비어있으면 진행
if q:
    result = tomato(q)

    # 안익은 토마토가 있는지 확인
    for idx, line in enumerate(box):
        if line.count(0) > 0:
            print(-1)
            break
   else:   
   		print(result)
        
# q가 비어있으면 토마토 익힐 수 없으니까 바로 -1 출력
else:
    print(-1)