링크:https://www.acmicpc.net/problem/7576
최소 날짜를 구해야 해서 bfs로 접근해 봤다
맨 처음 창고에서 익은 토마토(1)가 들어있는 정보를 담아 큐에 넣고 시작하여
상, 하, 좌, 우 체크하여 익지 않은 토마토(0)가 들어있으면 자신의 숫자의 +1을 더해 익지 않은 토마토에
대입해 준다
마지막에 리스트를 한번 순회하여 익지 않은 토마토(0)이 있으면 -1을 출력하고 프로그램 종료하고
창고 안에 토마토가 모두 익은 상태라면 창고에서 제일 큰 수를 구하여 -1을 해주어 출력한다
(맨 처음에 1로 시작했기 때문)
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
veclst = [(1,0),(-1,0),(0,-1),(0,1)]
n,m = map(int,input().split())
to = [list(map(int,input().split())) for _ in range(m)]
sav=[]
def bfs():
q = deque()
for y in range(m):
for x in range(n):
if to[y][x] == 1:
q.append([y,x])
while q:
now = q.popleft()
for vy,vx in veclst:
my,mx = now[0]+vy,now[1]+vx
if 0 <= my < m and 0 <= mx < n:
if to[my][mx] == 0:
to[my][mx] = to[now[0]][now[1]]+1
q.append([my,mx])
bfs()
s = -55
for x in to:
if 0 in x:
print(-1)
exit()
s = max(s,max(x))
print(s-1)
다른 방법으로는 토마토를 하나씩 꺼내지 않고 4방향을 확인하여 퍼진 토마토를 반복문으로 한 번에
퍼뜨리는 방법도 있는 거 같다 이쪽이 더 좋은 해결 방법인 것 같다
유익한 글이었습니다.