[백준] 7576 파이썬(python) : 토마토 - (★)

7576번: 토마토

 

 

from collections import deque
import sys
m, n = map(int, input().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
q = deque()
res = 0 #1
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i, j)) #2
bfs()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0: #3
            print(-1)
            exit(0) #4
        res = max(res, graph[i][j]) #5
print(res-1) #6

 

#1 : 결과값을 출력할 변수

#2 : 동시에 여러곳에서 토마토가 익어야 하니까 이중 for문으로 토마토가 있는 위치를 미리 모두 q에 담아둔다.

#3 : 모든 줄에 주변 토마토를 익힐 수 있을만큼 bfs를 끝냈으면 이중 for문으로 모든 위치에 0이 있는지 없는지 확인. 0이 하나라도 있으면 -1을 출력하고 프로그램 종료

#5 : 계속해서 최댓값 갱신

#6 : 토마토가 있는 위치를 정수 1로 시작했으니 가장 큰값은 최소가 걸린 일수에 +1이 되있는 상태. 그래서 -1을 해주고 출력

 

동시에 숫자를 기준으로 퍼지게 하는 방법을 bfs로 구현하는 방법을 새롭게 배울 수 있었다.

18405번: 경쟁적 전염과 비슷하다.