[백준] [Python] 7576번 토마토 - BFS

www.acmicpc.net/problem/7576

7576번: 토마토

 

Python

from collections import deque
#import time
import sys

#s = time.time()
col, row = map(int, sys.stdin.readline().split())

dq = deque()
dx = [0,0,1,-1]
dy = [1,-1,0,0]

tomato = []
visit = []
cnt = 0

for a in range(row):
    tomato.append(list(map(int, sys.stdin.readline().split())))
    visit.append([0]*col)
    for b in range(col):
        if tomato[a][b] == 0: visit[a][b] = -1
        if tomato[a][b] == 1: dq.append((a,b))

while (len(dq) != 0):
    #print(q)
    pos = dq[0]
    dq.popleft()
    
    for i in range(4):
        nx = pos[0] + dx[i]
        ny = pos[1] + dy[i]
        if (0<=nx<row and 0<=ny<col):
            if (visit[nx][ny] < 0): #and tomato[nx][ny] == 0):
                visit[nx][ny] =  visit[pos[0]][pos[1]]+1
                dq.append((nx,ny))
                cnt = max(cnt, visit[nx][ny])

for i in range(row):
    for j in range(col):
        if visit[i][j] == -1:
            print(-1)
            #print(time.time()-s)
            sys.exit(0)
        
print(cnt)
#print(time.time()-s)

 

 

풀이

• 시작점이 여러 개일 땐 그 점들을 모두 큐에 넣으면 된다.
• 처음에 리스트로만 구하려 했지만 어떻게 풀어보아도 시간 초과였다.
  • q.pop(0)는 O(n)만큼 느리지만 이 점을 고쳐도 소용은 없었다. (insert(0, v)도 그만큼 걸린다)

• collections의 deque를 이용하여 다시 풀었더니 해결되었다. 공식문서를 보니 리스트와 결과적으로 같으나 성능면에서 O(1)이라는 효율을 뽑을 수 있다고 되어있었다.

파이썬 deque 공식 문서

 

• deque에서도 똑같이 지원이 되는 함수들은 다음과 같다. 이번 코드에는 len(dq)를 이용했다. 인덱스로 접근할 때 중간 위치에 놓인 값을 찾을 때는 O(n)이 걸린다는 점에 유의하자 

 

 

 

• (사실 큐를 써서 풀면되는데 괜히 deque 공식 문서 좀 보려고 deque 쓴 것 뿐이다...! 큐로 쓰는 게 BFS에 더 맞다...!)