[BOJ 7576 - 토마토] BFS 알고리즘 (Python)

문제조건

• 하루가 지나면, 익은 토마토(1)의 인접한 토마토가 익는다(0 -> 1).
• 인접한 것은 아래, 위, 왼쪽, 오른쪽에 해당한다.
• 토마토가 모두 익는데 걸리는 최소 일수를 구하라.

핵심개념

• 익은 토마토(1) 여러 개에서 동시에 탐색을 시작하는 꼴이다.
• 처음에 익은 토마토들을 모두 queue에 넣고 탐색을 시작하자.

코드

from collections import deque
import sys
from functools import reduce

m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]

days = [[-1] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 안 익은 토마토가 없는 경우
tmp = reduce(lambda x, y: x + y, tomato)
if not 0 in tmp:
    print(0)
    sys.exit()

# 익은 토마토들을 queue에 모두 넣고 시작한다.
# 동시에 시작하는 정점들인 것이다.
q = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            days[i][j] = 0
            q.append((i, j))

# 탐색을 시작한다.
while q:
    x, y = q.popleft()
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            if tomato[nx][ny] == 0 and days[nx][ny] == -1:
                q.append((nx, ny))
                days[nx][ny] = days[x][y] + 1

for i in range(n):
    for j in range(m):
        # 탐색을 했는데도 안 익은 토마토가 있는 경우
        if tomato[i][j] == 0 and days[i][j] == -1:
            print(-1)
            sys.exit()

ans = max([max(row) for row in days])
print(ans)