[백준] 7576 토마토

https://acmicpc.net/problem/7576 

7576번: 토마토

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

m, n = map(int, input().split())
q = deque()
tomato = []
for r in range(n):
    tmp = list(map(int, input().split()))
    tomato.append(tmp)
    for c in range(m):
        if tmp[c] == 1:
            q.append((r, c))
count = 0
tmp_q = deque()
#delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
dy = [-1,1,0,0]
dx = [0,0,-1,1]

while q:
    r, c = q.popleft()
    for i in range(4):
        dr = r + dy[i]
        dc = c + dx[i]
        if 0 <= dr < n and 0 <= dc < m:
            if tomato[dr][dc] == 0:
                tomato[dr][dc] = 1
                tmp_q.append((dr,dc))
    if not q:
        q = tmp_q
        count += 1
        tmp_q = deque()
else:
    count -= 1
result = 0
break_chk = False
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            break_chk = True
            break
    if break_chk:
        break
if break_chk:
    result = -1
else:
    result = count
print(result)

이번엔 bfs를 사용했다.

dfs랑 큰 차이는 deque를 사용해서 앞에서부터 빼는것이 큰 차이다.

이문제에서는  queue가 비었을때 새로운 queue로 바꿔주는 작업을 하면서 count를 했다.

가장 큰 문제가 시간 초과였는데 delta를 사용해서 풀면 계속 시간초과가 걸렸고, dx, dy로 range를 돌렸더니 바로 해결이 되었다.

너무 허무하게 끝나서 내 한시간이......

for dt in delta 로 도는것보다 for i in range(4)로 접근하는게더 빠른걸 배워서 다행이다.