7576-토마토

문제

이 문제를 풀기 위해 무조건 BFS 알고리즘을 사용해야 된다는 것을 깨달았고, BFS를 전부 적용시킨 후, 아직 익지 않은 토마토가 있는지 확인하기 위한 for문을 돌려주면 쉽게 해결할 수 있다.

from collections import deque

def bfs(graph,start):
    queue = deque()
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    for i in start:
        queue.append(i)
    
    while queue:
        x,y = queue.popleft()

        for i in range(len(dx)):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>high-1 or ny >width-1 or nx<0 or ny<0:
                continue

            if(graph[nx][ny] == 0):
                queue.append([nx,ny])
                graph[nx][ny] = graph[x][y] + 1


width, high = map(int,input().split(' '))
tomato = []
find = []
isblank = False
for i in range(high):
    tomato.append(list(map(int,input().split(' '))))
for i in range(high):
    for j in range(width):
        if tomato[i][j] == 1:
            find.append([i,j])
bfs(tomato,find)
for i in range(high):
    for j in range(width):
        if(tomato[i][j] == 0):
            isblank = True
maximum = []
if isblank:
    print(-1)
else:
    for i in range(high):
        maximum.append(max(tomato[i]))
    print(max(maximum)-1)