백준 7576번 토마토1

최단거리 앞뒤 양쪽으로 이동을 통해 bfs문제라는것을 알 수 있다 이번 문제는 이전 문제들과 다르게 동시에 여러곳에서 탐색하는 경우의 수까지 고려해서 작성해야한다

입력에서 1이 여러개가 있으면 동시다발적으로 bfs가 실행되야 결과가 잘 나올 것이다 다른 문제에서는 한점으로 시작했지만 주어진 입력에 따라서 1이 여러개라면 하나씩 bfs를 돌리면 우리가 원하는 결과가 나오지 않는다 한번 bfs가 돌리고 끝날것임 그래서 처음 시작할 때 큐에 1이 있는 좌표를 모두 넣고 시작해서 번가라 가면서 bfs가 실행된다

from collections import deque
import sys
input = sys.stdin.readline

#리스트의 위치에는 0 -1 1세가지 경우가 있고 -1은 없는 경우 0은 변하기전 1은 익은 상태이다
#출력 결과 모두 익으면 최소 일수, 모두 익지 못하면 -1, 모두 익어있는 상태이면 0

dx=[-1,1,0,0]
dy=[0,0,1,-1]

m,n = map(int,input().split())
line =[]
q=deque()

for i in range(n):
    line.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        if line[i][j] == 1:
            q.append([i,j])

while q:
    x,y = q.popleft()
    
    for k in range(4):
        a = x + dx[k]
        b = y + dy[k]

        if a<0 or b<0 or a>=n or b>=m or line[a][b]== -1:
            continue

        if line[a][b]==0:
            line[a][b] = line[x][y] +1
            q.append([a,b])

#마지막 결과에서 -1을 해야한다 처음 1부터 시작하기 때문에     

cnt = 0 #결과에서 0을 셀때 사용한다
maax = 0


for i in range(n):
    for j in range(m):
        if line[i][j] == 0:
            cnt+=1

    if maax < max(line[i]):
        maax = max(line[i])

if cnt > 0 :
    print(-1)

else:
    print(maax-1)

 

마지막에서 최대값을 구할때 처음에 max(max(line)을 이용해서 결과를 구했는데 결과값이 틀렸다고 나왔다 예외적인 상황이 있을텐데 찾지 못하겠다

양쪽 방향에서 번갈아서 저장되고 실행되므로 양쪽이 동시에 수행된다고 생각할 수 있다