BOJ : 7576 토마토

익은 토마토들을 visit 에 저장하고 findUnRipenTomato() 를 통해 새로 익게되는 토마토들을 new_visit에 저장

만약 new_visit 이 비어있으면 while 문을 종료하고 비어있지 않으면 visit 으로 옮겨준 후 날짜(count)를 증가시킨 후 반복한다.

날짜가 증가될 때마다 checkTomatoAllRipen() 함수로 토마토가 다 익었는 지 확인하고 익었으면 new_visit 이 남아있더라도 while 문을 종료시키려고 했는데 시간초과.
매번 이중 for 문을 돌아야해서 더 비효율적인듯
그냥 방문할 토마토가 없을때까지 모두 체크하는 게 가장 빠르다.

import sys
from collections import deque


# 며칠이 지나면 토마토들이 모두 익는지
# 정수 1 은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 없는 칸

# x,y 위치에서 영향을 줄 수 있는 토마토들의 좌표를 출력
def findUnRipenTomato(x, y):
    pos_change = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    tom_unripen = []

    for i, j in pos_change:
        if 0 <= i + x < x_size and 0 <= j + y < y_size \
                and tomatoes[j + y][i + x] == 0:
            tom_unripen.append((i + x, j + y))
    return tom_unripen

# 토마토가 모두 익었는 지 확인
def checkTomatoAllRipen():
    global unripen
    x,y = unripen
    if tomatoes[y][x] == 0:
        return False
    for i in range(x_size):
        for j in range(y_size):
            if tomatoes[j][i] == 0:
                unripen = (i,j)
                return False
    return True


x_size, y_size = list(map(int, list(sys.stdin.readline().strip().split())))
tomatoes = [list(map(int, list(sys.stdin.readline().strip().split()))) for _ in range(y_size)]

unripen = (0,0)
visit = deque([])
new_visit = deque([])
count = 0

for i in range(x_size):
    for j in range(y_size):
        if tomatoes[j][i] == 1:
            visit.append((i, j))
# print(visit)
# visit 엔 익은 토마토의 (x,y) 좌표값들이 들어있음
allRipen = False
while True:
    while visit:
        cur_x, cur_y = visit.popleft()
        # print(cur_x,cur_y)

        for (x, y) in findUnRipenTomato(cur_x, cur_y):
            tomatoes[y][x] = 1
            new_visit.append((x, y))

    if not new_visit:
        break
    visit = new_visit
    new_visit = deque([])
    count += 1

if checkTomatoAllRipen():
    print(count)
else:
    print(-1)