[백준/Python] 7576 토마토

 

 

 

• 배열 완전탐색을 통해 초기의 1의 인덱스값들을 저장 한 후 bfs를 통해 Max값을 구했다.
• bfs를 전부 돌고 난 후 완전탐색을 통해서 익지 않은 토마토가 있는 경우 (0)가 있다면 -1을 출력하도록 했다.

from collections import deque

M,N = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
used = [[0]*M for _ in range(N)]
q = deque()
Max = -21e8
for j in range(N):
    for i in range(M):
        if arr[j][i] == 1:
            q.append([j,i]) # 1의 인덱스값을 저장
            used[j][i] = 1

def bfs():
    global Max
    directy = [-1,1,0,0]
    directx = [0,0,-1,1]

    while q:
        y,x = q.popleft()
        if arr[y][x] > Max: 
            Max = arr[y][x] # bfs를 돌면서 Max값을 갱신

        for k in range(4):

            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어난다면 continue
                continue
            if arr[dy][dx] == -1: # 토마토가 들어 있지 않다면 continue
                continue
            if used[dy][dx] == 0:
                used[dy][dx] = 1
                arr[dy][dx] = arr[y][x] + 1 # 목표 인덱스를 자신의 +1
                q.append([dy,dx])


bfs()
flag = 0
for j in range(N):
    for i in range(M):
        if arr[j][i] == 0: # 배열을 돌며 익지않은 토마토가 있을 시 flag = 1
            flag = 1

if flag == 1:
    print("-1")
else:
    print(Max-1)