백준 7576 토마토

import sys
from collections import deque

n,m=map(int,sys.stdin.readline().split())
graph=[list(map(int,sys.stdin.readline().split()))for i in range(m)]
dir=[[0,1],[1,0],[0,-1],[-1,0]]
visited=[[0 for i in range(n)]for i in range(m)]
queue=deque()

for i in range(m):
    for j in range(n):
        if graph[i][j]==1:
            queue.append((i,j))
            visited[i][j]=1


def is_eqaul():
    for i in range(m):
        for j in range(n):
            if graph[i][j]==0:
                return 0
    return 1

def BFS_iter():

    while queue:
        x,y=queue.popleft()
        visited[x][y]=1

        if is_eqaul():
            max_value=-1
            for i in range(m):
                for j in range(n):
                    if max_value<graph[i][j]:
                        max_value=graph[i][j]
            print(max_value-1)
            break

        for i in range(4):
            dx=x+dir[i][0]
            dy=y+dir[i][1]

            if dx<0 or dx>=m or dy<0 or dy>=n:
                continue

            if graph[dx][dy]==-1:
                continue

            if visited[dx][dy]==0:
                visited[dx][dy]=1
                graph[dx][dy]=graph[x][y]+1
                queue.append((dx,dy))
    else:
        print(-1)


BFS_iter()

링크텍스트

토마토 문제는

6 4

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

0 이 안익은 토마토 1이 익은 토마로 라 했을때 토마토는 상,하,좌,우로 익어간다. 그렇게 됐을때 전체 토마토가 익었을때 최단 시간을 찾는문제다.

-1은 벽으로 전체가 못익을 경우 -1을 print 한다.

​

나는 그냥 단순하게 초기 상태에서 1인 값들의 x,y 값을 큐에 넣어 줬다. 그리고 그 큐안에 있는 값들로 BFS 를 시작하여 최종적으로 BFS 가 다 돌았을때 칸을 비교하여 0이 있으면 -1 없으면 count 의 값을 출력해준다.