https://www.acmicpc.net/problem/7576
알고리즘 자체는 처음부터 제대로 작성하였다. 하지만, 몇 번의 시간 초과와 런타임 에러를 겪고 배운 것들을 정리하고자 한다.
exit(1)
을 사용한다. list.pop(0)
은 첫 번째 요소를 pop한 후 나머지 요소를 앞으로 한 칸씩 당기므로 O(N)의 시간이 걸린다. 상관 없다면 list.pop()을 사용하자.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)