[Python] 백준 7576번 토마토

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

7576번: 토마토

 

풀이 방법

1. BFS 이용해서 시간 구하고,

2. for문 돌려서 0이 나오면 return -1, 아니면 T 반환.

 

 

Code

from collections import deque
# import sys
# input = sys.stdin.readline
 
def solve(n, m, board):
    queue = deque()
    for i in range(m):
        for j in range(n):
            if board[i][j] == 1: queue.append([i, j, 0]) # x, y, 시간
    # 동 남 서 북
    dxs = (0, 1, 0, -1)
    dys = (1, 0, -1, 0)
 
    while queue:
        x, y, t = queue.popleft()
        T = t
        for dx, dy in zip(dxs, dys):
            nx, ny = x+dx, y+dy
            if nx<0 or nx>=m or ny<0 or ny>=n: continue
            if board[nx][ny] == 0:
                board[nx][ny] = 1
                queue.append([nx, ny, t+1])
    for i in range(m):
        for j in range(n):
            if board[i][j] == 0:
                return -1
    return T
 
 
if __name__ == '__main__':
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(m)]
    print(solve(n, m, board))