[BOJ] (BFS)7576번 토마토

전형적인 bfs문제.

시간이라는 개념이 문제에 섞여있는데, 큐에 좌표와 day까지 같이 넣어주면 된다.

최종 걸린 시간은, 큐가 끝날 때의 day가 된다. 

from collections import deque

def main():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    m, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    q = deque()
    
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                q.append((i, j, 0))
                
    while q:
        x, y, day = q.popleft()
        
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            nday = day+1
            
            if not (0<=nx<n and 0<=ny<m):
                continue
                
            if arr[nx][ny] == 0:
                arr[nx][ny] = 1
                q.append((nx, ny, nday))
                
    
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                return -1
            
    return day

print(main())

 

 

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

7576번: 토마토