백준 7576) 토마토 (골드.5)

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

7576번: 토마토

 

문제의 조건을 확인하면 다음과 같다. 썩은 토마토부터 시작해서 전체를 다 탐색할 때까지 걸리는 시간을 구하는 BFS문제다. 

1) 썩은 토마토는 1, 썩지 않은 토마토는 0, 토마토가 없는 곳은 -1로 주어진다. 

3) 썩은 토마토는 하루가 지나면 인접해있는 앞뒤왼오의 네 방향의 토마토도 썩게 만든다. 

2) 토마토가 모두 썩을 수 없으면 -1을 반환

3) 토마토가 모두 썩을 때까지 걸리는 날짜를 출력 

 

 

다음과 같이 BFS를 이용하였다. 

from collections import deque
global m, n, tomato, day
m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
answer = 0
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def find_first_rotten_tomato(queue):
    global m, n, tomato
    for a in range(n):
        for b in range(m):
            if tomato[a][b] == 1:
                queue.append((a, b, 0))
    return queue

def check_all_rotten():
    global m, n, tomato
    for a in range(n):
        for b in range(m):
            if tomato[a][b] == 0:
                return False
    return True

def bfs():
    global m, n, tomato, answer
    queue = find_first_rotten_tomato(deque())
    if len(queue) == 0:
        answer = -1
        return 
    while queue:
        y, x, day = queue.popleft()
        answer = day
        for k in range(4):
            ny = y + d[k][0]
            nx = x + d[k][1]
            if 0<=ny<n and 0<=nx<m and tomato[ny][nx]==0:
                tomato[ny][nx] = 1
                queue.append((ny,nx, day+1))
    if not check_all_rotten():
        answer = -1
        
bfs()     
print(answer)