[백준 / Python] 7576 - 토마토

백준 7576 토마토

Intro

Solution

1. 방향을 지정한 리스트를 미리 선언하고, 입력받은 토마토의 위치를 큐를 만들어 집어넣는다.
2. 너비 우선 탐색을 한다.
3. 익지 않은 토마토를 토마토를 익힐 때마다 1을 더하며 그래프를 갱신한다.
4. 그래프에서 가장 큰 값이 토마토를 모두 익히는데 필요한 최소 날짜이다.
5. 익지 않은 토마토 즉 그래프에 0이 있을 경우 -1을 출력한다.

Code

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

def solve():
	m, n = map(int, input().split())
	farm = [[*map(int, input().split())] for _ in range(n)]
	
	queue = deque()
	dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	answer = 0

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

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

	bfs()

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


solve()