• 시간 복잡도 O(nm)으로 해결해야함

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

# 상하좌우
def ripe(i, j):
    if (j-1 >= 0) and tomatoes[i][j-1] == 0:
        tomatoes[i][j-1] = 1
    
    if (j+1 <= m-1) and tomatoes[i][j+1] == 0:
        tomatoes[i][j+1] = 1
        
    if (i-1 >= 0 ) and tomatoes[i-1][j] == 0:
        tomatoes[i-1][j] = 1
        
    if (i+1 <= n-1 ) and tomatoes[i+1][j] == 0:
        tomatoes[i+1][j] = 1

count = 0
prv = 0

while True:
    count += 1
    
    for i in range(n):
        for j in range(m):
            if tomatoes[i][j] == 1:
                ripe(i,j)

    riped = sum(row.count(1) for row in tomatoes)
    
    if riped == prv:
        break
    else:
        prv = riped
        
    if riped == n * m :
        break

print(count if prv == n * m else -1)

• 시간 복잡도 터짐O((nm)^2)

• 시간 복잡도 줄여야 됨
• 문제 조건에서, 익힐 수 있는 모든 인접한 토마토를 먼저 방문한다.
  • BFS의 특성과 일치, 최단 거리
• 각 토마토는 한번만 방문
  • O(nm)에 끝낼 수 있음

• queue를 사용하되, pop의 시간 복잡도를 O(1)로 하기 위해 deque 사용
• queue → 익은 토마토 → 인접한 노드를 모두 방문한 뒤에는 pop
• 우선적으로, 익어있는 토마토 모두 queue에 넣기
  • 좌표, 익은 날짜
• BFS 구현
  • queue가 빌 때까지 while 루프
    • queue 비었다 → 더 이상 방문할 노드가 없다.
    • queue에서 토마토를 pop
    • max_day 갱신
    • 해당 토마토와 인접한 상하좌우 토마토 모두 방문 및 queue에 push
      1. 방향 배열 선언
         1. 좌표 범위 체크
         2. 익을 수 있는지 체크

from collections import deque

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

# 처음부터 익어있는 토마토 위치를 큐에 넣기
queue = deque()
for i in range(n):
   for j in range(m):
       if tomatoes[i][j] == 1:
           queue.append((i, j, 0))  # (행, 열, 날짜)

# BFS
max_day = 0
while queue:
   i, j, day = queue.popleft()
   max_day = max(max_day, day)
   
   # 상하좌우 확인
   directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
   for x, y in directions:
		   x, y = x + dx, y + dy
       if 0 <= x < n and 0 <= y < m and tomatoes[x][y] == 0:
           tomatoes[x][y] = 1
           queue.append((x, y, day + 1))

# 덜 익은 토마토 확인
if any(0 in row for row in tomatoes):
   print(-1)
else:
   print(max_day)

• max_day를 굳이 갱신?