[알고리즘][Python] 백준 7576 토마토 문제 풀이

문제 출처 : www.acmicpc.net/problem/7576

7576번: 토마토

---

문제 해석 : 토마토가 익는 것은 익은 토마토로 부터 전파된다. 최소 몇일이 되어야 모든 토마토가 익을 수 있을까? 에 대한 문제이다.

 

문제 풀이 :  BFS를 통해서 문제를 풀 수 있다. 시간 초과에 유의하면서 차근차근 문제를 풀어 나가면 맞을 수 있다.

---

풀이 코드

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


def BFS():
    while Q:
        x,y = Q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <= ny < N:
                if arr[nx][ny] == 0:
                    arr[nx][ny] = arr[x][y] +1
                    Q.append((nx,ny))

N, M = map(int, input().split())
arr = []

for _ in range(M):
    arr.append(list(map(int, input().split())))

dx = [0,0,-1,1]
dy = [1,-1,0,0]
Q = deque()

for i in range(M):
    for j in range(N):
        if arr[i][j] == 1:
            Q.append((i,j))

BFS()

answer = 0
flag = False

for i in range(M):
    for j in range(N):

        if arr[i][j] == 0:
            flag = True
            break
        answer = max(answer, arr[i][j])

if flag:
    print(-1)
elif answer == -1:
    print(0)
else:
    print(answer-1)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.