[백준 파이썬] 7576번 토마토

백준 7576번 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

 

파이썬 풀이

import sys
import collections
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for i in range(M)]
queue = collections.deque() # bfs를 위한 queue 생성
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 좌표 이동

# graph 내에서 익은 토마토 위치 찾기
for i, j in enumerate(graph):
    if 1 in j:
        x,y = i,j.index(1) # 익은 토마토 위치
        queue.append([x,y]) # queue에 익은 토마토 삽입


# bfs
while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] == 0:
            queue.append([nx,ny])  # queue에 삽입
            graph[nx][ny] = graph[x][y] + 1 # grpah 갱신

flag = False # 안 익은 토마토 존재 여부 판단 flag
result = -2 # 임의의 최소값

for i in graph:
    for j in i:
        if j == 0:
            flag = True
        result = max(result,j) # 결과값 갱신

if flag == True:
    print(-1)
elif result == -1:
    print(0)
else:
    print(result-1)