[Python] 백준7576번 : 토마토

💡문제

백준 7576번 문제 링크

🍀풀이

이 문제 같은 경우엔 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익은 토마토에게 영향을 받아 익게 되는거니까 BFS로 풀 수 있다.
그리고 예제를 보면 익은 토마토가 한 개만 있는게 아니라 두 개가 있는 것도 있기 때문에 기존에 하던 방식처럼 시작점 하나를 넣고 bfs를 돌리면 안된다. 이렇게 시작점이 여러개인 경우엔 시작점을 다 Queue에 넣고 bfs를 돌리면 된다!

코드

import sys
from collections import deque
input = sys.stdin.readline

m,n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

queue = deque()

# 시작점이 여러개인 경우엔 시작점을 모두 Queue에 넣어야 함!
# 익은 토마토들을 Queue에 다 넣기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

def bfs():
    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:
                queue.append([nx, ny])
                graph[nx][ny] = graph[x][y] + 1

bfs()

result = 0

# for문을 돌려서 안익은 토마토가 있으면 -1 출력하고 종료하고
# 다 익었으면 최대값 출력
for i in graph:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    result = max(result, max(i))

print(result - 1) # 익은 토마토 1로 시작했으니 -1 해줘야함

풀면서 주석을 달았는데 for문을 돌려서 익은 토마토를 큐에다가 넣고, 안 익은 토마토가 있으면 -1 바로 출력해서 종료하고, 다 익었으면 최대값을 출력해주는 식으로 풀었다.