백준 7576번 토마토 파이썬 BFS

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

7576번: 토마토

 

내 답안

from collections import deque
import sys

input = sys.stdin.readline

M, N = map(int, input().rstrip().split())
tomato = [list(map(int, input().rstrip().split())) for i in range(N)]
date = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            q.append((i, j))
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= N or ny >= M:
            continue

        if tomato[nx][ny] == 1:
            continue

        if tomato[nx][ny] == 0:
            tomato[nx][ny] = 1
            date[nx][ny] = date[x][y] + 1
            q.append((nx, ny))

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 0:
            print(-1)
            sys.exit(0)
result = 0
for i in range(N):
    for j in range(M):
        if result < date[i][j]:
            result = date[i][j]
print(result)

---

 

예제 입력 1로 설명을 하면

일단 주어진 tomato를 리스트에 담는다.

그리고 tomato 크기와 똑같고, 0으로 초기화된 date 라는 명을 가진 리스트를 만든다.

 

1.  처음에는 입력받은 tomato들 중 1인 좌표를 q에 넣어주었다.   q = [(3, 5)]

step1

 

2.  q에 있는 원소를 popleft() 하여 BFS를 진행 해준다.   q = [(2, 5), (3, 4)]

step2

 

3.  2번을 반복 해준다.   q = [(1, 5), (2, 4), (3, 3)]

step3

.

.

.

.

 

final step.  q 가 빌 때까지 반복을 해준다면 마지막 과정은 아래와 같이 된다.   
q = []

final step

 

마지막 출력은 date 를 다 순회 하면서 최댓값을 찾으면 된다.

 

만약 0이 tomato 안에 0이 하나라도 존재하면 다 익지 못한 상태니까, 

sys.exit(0)을 하여 -1을 출력하고 프로그램을 정상적으로 종료 시켜준다.