boj.kr/7576 토마토 (gold5) 파이썬 풀이

1. deque에 익은 토마토 좌표를 모두 저장
2. dfs 방식으로 deque를 검사하면서 상화좌우 안익은 토마토는 현재토마토 좌표의 값의 + 1의 값을 갖도록 저장
3. 익은 토마토로 변경된 토마토의 좌표를 deque에 저장
4. 전제 좌표 값을 순회하면서 0이 있으면 -1을 출력, 0이 없으면 좌표 값 중에서 최대-1을 출력

 

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

from collections import deque
dq = deque()
for y in range(N):
    for x in range(M):
        if board[y][x] == 1:
            dq.append((y, x))

dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
def bfs():
    while dq:
        (cy, cx) = dq.popleft()
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<M and board[ny][nx] == 0:
                board[ny][nx] = board[cy][cx] + 1
                dq.append((ny, nx))
    max_cnt = -1e9
    for row in board:
        if row.count(0) > 0:
            return -1
        else:
            max_cnt = max(max_cnt, max(row))
    return max_cnt-1

print(bfs())

 

먼저 익은 토마토의 좌표들을 dq에 저장해두고 bfs탐색을 통해 경과일수를 저장해야 한다.

익은 토마토 값인 1 에서 시작했으므로 저장된 값-1을 해야 정확한 경과일수를 얻을 수 있다.