[Python] 백준 7576 - 토마토

문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

문제 해결방법

bfs 로 해결 가능하다.

입력 조건으로 토마토는 1개이상이 들어갈수 있기 때문에 bfs 실행 전에 토마토의 위치를 큐에 넣어줘야 한다.
그 이후에 bfs 함수에서 인접열 방문시에 0(익지않은 토마토) 값이라면 기준열 토마토가 익는데 걸리시간에서 +1일을 해준다.

bfs 종료 후 만약 graph 내에 0이 아닌 값이 있다면 -1로 인해서 인접열 방문 실패한 경우이기 때문에 조건에 맞춰서 
-1 을 출력후 종료 그렇지 않다면 graph 내에 max_value-1이 답이다

문제 풀이

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().strip().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().strip().split(' '))))

queue = deque()
for i in range(M):
    for j in range(N):
        if graph[j][i] == 1:
            queue.append((i, j))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((nx, ny))

bfs()

max_value = 0
for i in range(M):
    for j in range(N):
        if graph[j][i] == 0:
            print(-1)
            exit()
        else:
            if max_value < graph[j][i]:
                max_value = graph[j][i]
print(max_value - 1)