[백준-7576] 토마토 / Python

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

7576번: 토마토

from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(m):
    graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()


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 ny < 0 or nx >= m or ny >= n:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))


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

bfs()

isTrue = False
answer = -2
for i in graph:
    for j in i:
        if j == 0:
            isTrue = True
        answer = max(answer, j)
if isTrue == True:
    print(-1)
else:
    print(answer - 1)

해설

알고리즘 문제를 해결할 때 제일 재밌는 파트가 BFS 문제다.

토마토가 있는 위치들을 먼저 deque에 저장하고 나서 BFS를 수행한다. 처음엔 이 부분을 캐치하지 못해서 틀렸다..😅

토마토가 있는 위치로부터 점점 퍼져나가면서 익은 토마토가 생기기 때문에 미리 deque에 익은 토마토 위치를 저장해야 한다.

BFS를 모두 수행하고 나서 graph 리스트에 0이 있으면 안익은 토마토가 있는 것이므로 flag를 True로 하고 -1을 출력한다. 토마토가 전부 익었다면 graph 리스트의 최댓값 - 1을 출력한다