[BaekJoon Online Judge] 7576 – 토마토

문제

https://www.acmicpc.net/problem/7576

소스코드

bfs를 이용한 최단거리 문제로 해결할 수 있다. 익은 토마토 옆이면 그 다음 사이클에 익은 상태로 바뀌기 때문에, 초기 상태에 익은 토마토 모두를 q에 넣은 뒤 bfs 탐색을 시작한다. 탐색이 끝나면 visit 배열에서 가장 높은 숫자가 상자 내의 모든 토마토가 익는 최소 날짜가 된다.

from collections import deque

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

M,N = map(int,input().split())
field = [list(map(int,input().split())) for _ in range(N)]

visit = [[0 for _ in range(M)] for _ in range(N)]

q = deque()
for i in range(N):
    for j in range(M):
        if field[i][j] == 1:
            q.append((i,j))
            visit[i][j] = 0

while q:
    x,y = q.popleft()
    for i in range(4):
        to_x,to_y = x+dx[i],y+dy[i]
        if to_x>=0 and to_y>=0 and to_x<N and to_y<M:
            if field[to_x][to_y] == 0 and visit[to_x][to_y] == 0:
                q.append((to_x,to_y))
                visit[to_x][to_y] = visit[x][y] + 1

ripe = True
for i in range(N):
    for j in range(M):
        if field[i][j] == 0 and visit[i][j] == 0:
            ripe = False
            break

if ripe:
    ans = 0
    for i in range(N):
        for j in range(M):
            if ans < visit[i][j]:
                ans = visit[i][j]
    print(ans)
else:
    print(-1)