문제 링크

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

문제 설명

• board에 썩은 토마토 위치가 주어진다

• 인접해있을 경우 하루마다 주변 토마토가 썩는다

• 비어있는 칸이 있다

• 모두 썩지 않으면 -1

• 모두 썩으면 최대 일 수 출력

풀이

• BFS로 거리에 따라 탐색

• 마지막에 남은 0이 있는지 체크

• 있으면 -1 출력

• 없으면 최대 일 수 출력

• 예시 1 최종 리스트
  

• 예시 2 최종 리스트
  

코드

from collections import deque
import sys


def init():
    ipt = sys.stdin.readline
    w, h = map(int, ipt().split())
    board = [list(map(int, ipt().split())) for _ in range(h)]
    dy, dx = [1,-1,0,0], [0,0,1,-1]
    return h, w, board, -1, dy, dx


def bfs():
    global max_day
    q = deque()
    for y in range(h):
        for x in range(w):
            if board[y][x] == 1:
                q.append((y, x))
    while q:
        cy, cx = q.popleft()
        max_day = max(max_day, board[cy][cx]) - 1
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if 0 <= ny < h and 0 <= nx < w:
                if not board[ny][nx]:
                    board[ny][nx] = board[cy][cx] + 1
                    q.append((ny, nx))


h, w, board, max_day, dy, dx = init()
bfs()
if all([all(row) for row in board]):
    print(max_day)
else:
    print(-1)