[Algorithm] 백준 7576 - 토마토 in Python(파이썬)

💡 백준 7576:

BFS 탐색을 통해 토마토가 모두 익는 최소 날짜 탐색하기

🌱 코드 in Python

알고리즘: BFS

from collections import deque
import sys

input = sys.stdin.readline
m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
d = deque([])
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for i in range(n):
	for j in range(m):
		if g[i][j] == 1:
			d.append([i, j]) # 익은 토마토가 동시적으로 확산을 시작해야 하므로 시작하는 덱에 익은 토마토 다 넣기

def bfs():
	while d:
		cx, cy = d.popleft()
		for x, y in zip(dx, dy):
			nx = cx + x
			ny = cy + y
			if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 0:
				g[nx][ny] = g[cx][cy] + 1 # 익은 날짜 갱신
				d.append([nx, ny])

bfs()

ret = 0
for i in g:
	if 0 in i:
		print(-1) # 토마토 밭에 익지 않은 토마토가 하나라도 있으면 -1 출력 후 브레이크
		break
	ret = max(ret, max(i)) # 토마토 밭을 순회하며 맥스값 갱신

else:
	print(ret - 1)

이 문제는 토마토 밭의 토마토가 모두 익을 때까지의 '최소'날짜를 탐색하는 문제로 역시 BFS를 사용하면 해결 할 수 있는 문제였다

다만 기존의 BFS와 다른 점은 출발지가 여러개일 수 있다는 것으로, 기존엔 0, 0과 같이 시작 지점을 하나만 지정해주었다면,
이번 문제는 맵에서 1인 지점을 다 저장해두고 시작해야 한다

🧠 기억하자

1. for-else 문을 잘 생각하자!

백준 7576 바로가기