코테 백준 7576 골드5

백준 7576

이문제를 풀때 처음 고민한게 1인 토마토들이 동시에 bfs를 실행해야하지않나? 예를들면 왼쪽 끝과 오른쪽 끝에있는 사람이 동시에 출발해서 중앙에서 만날때 최소시간이지 왼쪽사람이 오른쪽 끝까지 가서 만나면 시간이 더 오래걸리는것처럼 어떻게 구현해야하지? 라고 생각했다.

여기서 포인트는 이러한 점때문에 dfs를 하면 안된다는 점이다. 이때까지 내가 풀었던 bfs문제들은 dfs문제들로 풀어도 괜찮았다. 하지만 이번문제는 깊이 들어가면 내가 아까 고민했던것처럼 시간이 오래걸린다. 그래서 bfs를 이용해서 주변탐색으로 가야한다. bfs를 이용해서 동시에 실행을하는것은 불가능하지만 순차적으로 1인위치들부터 시작하고 그다음에 서로 퍼지는 방식이다. 그래서 그중 가장 큰값을 가지는값을 찾아서 답을 구해준다. 풀이방법은 이전의 bfs와 같다.

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

m,n=map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(n)]
que=deque()

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

def bfs():
    while que:
        y,x=que.popleft()
        for i in range(4):
            new_dy=y+dy[i]
            new_dx=x+dx[i]
            if (0<=new_dx<m) and (0<=new_dy<n) and graph[new_dy][new_dx]==0:
                que.append((new_dy,new_dx))
                graph[new_dy][new_dx]=graph[y][x]+1

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

bfs()
total=0
for i in range(n):
    for j in range(m):
        if graph[i][j]==0:
            print(-1)
            exit()
        total=max(total,graph[i][j])

print(total-1)