[백준] 7576번: 토마토

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

7576번: 토마토

 

 

bfs로 최단거리 탐색을 활용하면 쉽게 풀 수 있다. 이 문제를 풀면서 list로 pop,append를 사용하는 것 보다 deque()로 선언을 하여 돌려주는 것이 훨씬 빠르다는 것을 알았다.(list로 pop을 할 때 전체 list를 서치하게 됨)

 

from collections import deque

m,n = map(int,input().split())

arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))


q = deque([])

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q.append([i,j])


dx, dy = [-1,1,0,0], [0,0,-1,1]
while q:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<= nx < n and 0<= ny < m and arr[nx][ny] == 0:
            arr[nx][ny] = arr[x][y] + 1
            q.append([nx,ny])

max = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            print("-1")
            exit(0)
        if max < arr[i][j]:
            max = arr[i][j]

print(max-1)