[파이썬, Python] 백준 7576: 토마토

문제

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

7576번: 토마토

코드

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

m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = 0

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

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

bfs()

for i in tomato:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    ans = max(ans, max(i))
print(ans - 1)

설명

collections에서 deque을 사용하는데(Queue),
pop보다 popleft의 시간 복잡도가 훨씬 낮기 때문이다(O(n)과 O(1)의 차이).

토마토의 리스트를 받아주고,
bfs에 사용할 큐를 위한 deque도 하나 생성해 준다.
dx, dy로 이동 범위를 지정해 주고,
답을 카운트할 ans도 만들어준다.

반복문을 돌면서 좌표의 값이 1이면(토마토가 있으면)
큐에 넣고 bfs를 돌려준다.

bfs는 일반적으로 많이 사용하는 공식을 그대로 사용했다.
상하좌우로 움직이고,
범위를 벗어나는 경우에 대해서는 고려하지 않으며,
연결된 범위에 대해 탐색을 계속 진행해 준다.

이때 수가 1씩 늘어나는데,
1씩 늘어남에 따라 하루가 추가로 진행된다고 생각하면 된다.

bfs가 종료된 후,
토마토의 리스트에 0이 남아있다면 -1을 출력하고 프로그램을 종료한다.
0이 남아있지 않다면 완벽하게 익었으므로 ans에서 1을 뺀 값을 출력한다.
(bfs의 첫 시작이 1이었으므로 0일에 이미 익어있던 경우를 고려한다.)