[Algorithm] 백준 7576 토마토 | 파이썬 BFS

※ 7576 토마토

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

문제 해결 TIP

이코테의 미로 탈출과 비슷한 문제라고 생각했다. BFS를 이용하여 토마토를 전염시킨 후 최단 거리를 반환하는 것과 같이 전염하면서 이전 값에 1을 추가하여 값을 저장하도록 한다. 이때 주의할 점은 2차원 배열의 첫번째 원소부터 탐색 시작하는 것이 아닌, 1을 가진 토마토라면 동시에 전염이 시작되어야 한다는 것이다. 최종적으로 바뀐 2차원 배열 graph에 익지 않은 토마토가 있다면 -1을 반환하고 그렇지 않으면 최소 일수(graph에서 가장 큰 원소값-1)를 반환한다. 이때 이미 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하게 되어있는데, 어차피 graph에서 가장 큰 원소값이 1일테니 0을 반환할 것이므로 따로 코드를 작성하지 않았다.

 

전체 코드

from collections import deque

M, N = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

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

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

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

# BFS 수행
bfs(graph)

# 결과 확인
days = 0
for row in graph:
    if 0 in row:  # 익지 않은 토마토가 남아있으면
        print(-1)
        break
    days = max(days, max(row))
else:
    # 처음 시작이 1이므로 1을 빼줘야 한다
    print(days - 1)