7576 토마토

Python

from collections import deque
tomato_que = deque()
move = ((-1, 0), (0, -1), (1, 0), (0, 1))
def main():
    column, row = map(int, input().split())#열, 행
    box = []
    global tomato_que

    for i in range(row):
        column_tomato = list(map(int, input().split()))
        box.append(column_tomato)

        for index, tomato in enumerate(column_tomato):
            if tomato == 1:
                tomato_que.append((i, index, 0))#x, y, day

    print(bfs(box))
    
def bfs(box):
    global tomato_que
    global move
    max_day = 0

    while tomato_que:
        x, y, day = tomato_que.popleft()

        for m in move:
            dx, dy = x + m[0], y + m[1]
            # print(dx, dy)
            if dx < 0 or dx >= len(box) or dy < 0 or dy >= len(box[0]):#범위 넘어갔을 때
                continue

            if box[dx][dy] == 0:#토마토 있을 때
                box[dx][dy] = 1
                tomato_que.append((dx, dy, day + 1))
                max_day = day + 1
    

    for b in box:
        if 0 in b:
            return -1
    return max_day
        

     

# 메모리 초과
# import sys
# limit_number = 1000 * 1000
# sys.setrecursionlimit(limit_number)
# day = 0
# move = ((-1, 0), (0, -1), (1, 0), (0, 1))
# def main():
#     global day
#     column, row = map(int, input().split())#열, 행
#     box = []
#     tomato_space = []

#     for i in range(row):
#         column_tomato = list(map(int, input().split()))

#         for index, tomato in enumerate(column_tomato):
#             if tomato == 1:
#                 tomato_space.append((i, index))
#         box.append(column_tomato)


#     # print(box)
#     # print(tomato_space)

#     box = start_day(box, tomato_space)
#     for column in box:
#         if 0 in column:
#             print(-1)
#             return
#     print(day)

# def start_day(box, tomato_space):
#     global move
#     global day
#     find_ = False
#     tomato_space2 = []
#     # print(box, tomato_space)
#     for space in tomato_space:
#         x, y = space
#         for m in move:
#             # print(x, m)
#             if not ((x + m[0] >= 0 and x + m[0] < len(box)) and\
#                     (y + m[1] >= 0 and y + m[1] < len(box[0]))):#범위를 넘어갔을 때
#                 continue
#             if box[x + m[0]][y + m[1]] == 0:
#                 find_ = True
#                 box[x + m[0]][y + m[1]] = 1
#                 tomato_space2.append((x + m[0], y + m[1]))
#             else:
#                 continue
    
#     if find_:
#         day += 1
#         box = start_day(box, tomato_space2)
    
#     return box

main()