백준 7576번: 토마토 (파이썬, BFS)

개인적으로 좀 어려웠던 문제였다. 왜냐하면 쉬운 BFS문제들은 보통 탐색을 한 회 할 때마다 카운트를 늘리면 되는데, 이 문제는 한 계층을 다 탐색한후에 카운트를 늘려야 했기 때문이다. 왜냐하면 1초가 지날때, 익은 토마토 주변의 토마토들이 모두 익기때문이다.

 

따라서 1초마다 익은 토마토 주변의 모든 토마토가 익는다는것을 구현하기 위해 입력받은 값에서 값이 1인 값들을 새로운 배열에 저장하고, 그 배열을 BFS의 입력으로 썼다. 

 

그리고 while문 안에도 빈 배열을 선언하였는데, 입력받은 값들 중 값이 1인값들 주변을 탐색하였을 때 1초후에 값이 1이 되는 값들(0)을 배열에 모아 덱에 저장하기 위함이다. 

 

이렇게 덱에 있는 원소(배열)를 다 탐색한 후에 카운트를 늘리면 통과한다. 또한 모두 익지는 못했을때를 판별하기 위하여 BFS로 배열 전체를 탐색한 후에도 0인 값이 남아있다면 -1를 출력 후 프로그램을 종료하도록 sys.exit를 사용하였다.

 

import sys
from collections import deque


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


def bfs(tomatoes):
    global cnt
    q = deque([tomatoes])
    while True:
        now = q.popleft()
        if len(now) == 0:
            break
        cache = []
        for cac in now:
            xx, yy = cac
            for i in range(4):
                nx = xx + dx[i]
                ny = yy + dy[i]
                if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    visited[nx][ny] = True
                    cache.append((nx, ny))
        q.append(cache)
        cnt += 1


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

visited = [[False]*M for __ in range(N)]

for row in range(N):
    for col in range(M):
        if graph[row][col] == 1:
            tomato.append((row, col))

bfs(tomato)

for row_ in range(N):
    if 0 in graph[row_]:
        print(-1)
        sys.exit(0)

print(cnt-1)