[BOJ] 7576 토마토

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

알고리즘 자체는 처음부터 제대로 작성하였다. 하지만, 몇 번의 시간 초과와 런타임 에러를 겪고 배운 것들을 정리하고자 한다.

• 백준에서 파이썬으로 문제를 풀 때, 프로그램을 바로 끝내려면 exit(1)을 사용한다.
• list.pop(0)은 첫 번째 요소를 pop한 후 나머지 요소를 앞으로 한 칸씩 당기므로 O(N)의 시간이 걸린다. 상관 없다면 list.pop()을 사용하자.
• 큐를 활용할 때 리스트를 이용하는 것보다 deque가 눈에 띌 정도로 빠르다. 표준 라이브러리를 적극적으로 활용하자

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

N, M = map(int, input().split())
arr = [list(map(int,input()[:-1].split())) for _ in range(M)]
dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
queue = deque()

for j in range(N):
    for i in range(M):
        if arr[i][j] == 1:
            queue.append((i,j))

while queue:
    this_x, this_y = queue.popleft()
    for ddx, ddy in zip(dx, dy):
        x, y = this_x + ddx, this_y + ddy
        if 0 <= x < M and 0 <= y < N:
            if arr[x][y] == 0:
                arr[x][y] = arr[this_x][this_y] + 1
                queue.append((x, y))

answer = 0
for i in range(M):
    for j in range(N):
        answer = max(answer, arr[i][j])
        if arr[i][j] == 0:
            print(-1)
            exit(0)

print(answer - 1)