[Python] 백준 <7576-토마토>

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

 

- 오답 코드 (시간 초과)

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

def bfs(tomato_map):
    dq = deque()
    for i in range(N):
        for j in range(M):
            if tomato_map[i][j] == 1:
                dq.append((i, j))
    
    cursor = [(-1,0), (1,0), (0,-1), (0,1)]
    change = False
    while dq:
        x, y = dq.popleft()
        for dx, dy in cursor:
            nx, ny = x + dx, y + dy
            # 사방으로 토마토 안 익었으면 익게 하기
            if 0 <= nx < N and 0 <= ny < M and tomato_map[nx][ny] == 0:
                tomato_map[nx][ny] = 1
                change = True
    # 새로 익은 토마토가 없으면 False 반환
    return change

M, N = map(int, input().split(" "))
tomato_map = []
for _ in range(N):
    tomato_map.append(list(map(int, input().split(" "))))

days = 0
while True:
    new_tomato = bfs(tomato_map)
    if new_tomato:
        days += 1
    else:
        break

zero = False
for line in tomato_map:
    if 0 in line:
        zero = True

if zero:
    print(-1)
else:
    print(days)

 

- 정답 코드 (deque에 day 같이 저장)

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

def bfs(tomato_map):
    dq = deque()
    max_day = 0
    zero_count = sum(row.count(0) for row in tomato_map)
    for i in range(N):
        for j in range(M):
            if tomato_map[i][j] == 1:
                dq.append((i, j, 0))
    
    cursor = [(-1,0), (1,0), (0,-1), (0,1)]
    while dq:
        x, y, day = dq.popleft()
        max_day = max(max_day, day)
        for dx, dy in cursor:
            nx, ny = x + dx, y + dy
            # 사방으로 토마토 안 익었으면 익게 하기
            if 0 <= nx < N and 0 <= ny < M and tomato_map[nx][ny] == 0:
                tomato_map[nx][ny] = 1
                zero_count -= 1
                dq.append((nx, ny, day+1))

    # 마지막으로 바뀐 일수와 남은 0 개수 반환
    return max_day, zero_count

M, N = map(int, input().split(" "))
tomato_map = []
for _ in range(N):
    tomato_map.append(list(map(int, input().split(" "))))

days, zero_cnt = bfs(tomato_map)

if zero_cnt == 0:
    print(days)
else:
    print(-1)