1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | from collections import deque
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
def bfs(q):
global n, m
while q:
curr = q.popleft()
for d in direction:
next_y = curr[0] + d[0]
next_x = curr[1] + d[1]
if 0 <= next_y < n and 0 <= next_x < m and visit[next_y][next_x] == 0:
visit[next_y][next_x] = curr[2] + 1
q.append((next_y, next_x, curr[2] + 1))
m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]
visit = box[:]
queue = deque()
for i in range(n):
for j in range(m):
if box[i][j] == 1:
queue.append((i, j, 1))
bfs(queue)
max_val = cnt_zero = 0
for v in visit:
cnt_zero += v.count(0)
max_val = max(max_val, max(v))
if cnt_zero > 0:
max_val = -1
else:
max_val -= 1
print(max_val)
|
파이썬에서 pop(0) 을 하게되면 (O(n)) 의 복잡도로 시간이 오래걸린다. 따라서 deque 모듈을 사용한다.
댓글
댓글 쓰기