백준 7576번 : 토마토 (Python)

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

7576번: 토마토

 

풀이

먼저 반복문을 돌아 notyet에 익지 않은 토마토 개수를 저장하고, 익은 토마토를 큐에 쌓는다.

큐에서 pop했을 때 상하좌우중 익지 않은 토마토(0)일 경우 0을 익은 토마토의 넘버 + 1로 변경한 뒤 좌표를 큐에 쌓는다.

큐가 끝났는데 notyet이 남아있다면 -1, 아니라면 마지막 토마토 넘버 - 1 을 출력한다.

from collections import deque

M, N = map(int, input().split())                  # 입력
tomato = []
for i in range (N):
    tomato.append(list(map(int, input().split())))

que = deque()                                     # 초기화
notyet = 0
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 0:
            notyet += 1
        if tomato[i][j] == 1:
            que.append((i,j))
a = [1,-1,0,0]
b = [0,0,1,-1]


while que:                                        # 실행
    x,y = que.popleft()
    day = tomato[x][y]-1

    for i in range(4):
        if 0<=x+a[i]<N and 0<=y+b[i]<M:
            if tomato[x+a[i]][y+b[i]] == 0:
                tomato[x+a[i]][y+b[i]] = tomato[x][y]+1
                que.append((x+a[i],y+b[i]))
                notyet -= 1
                


if notyet == 0:
    print(day)
else:
    print('-1')