토마토 (7576)

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

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().rstrip().split())

def result_check(map_list, ct):
    for i in range(N):
        for j in range(M):
            if map_list[i][j] == 0:
                return -1
    return ct

map_list = []
queue = deque()
for i in range(N):
    now_list = list(map(int, input().rstrip().split()))
    map_list.append(now_list)
    for j in range(M):
        if now_list[j] == 1:
            queue.append((i,j))

ct = 0
while queue:
    next_queue = deque()    
    
    while queue:
        a, b = queue.popleft()
        for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
            n_a, n_b = a+m_a, b+m_b
            if (0 <= n_a < N) and (0 <= n_b < M) and (map_list[n_a][n_b] == 0):
                map_list[n_a][n_b] = 1
                next_queue.append((n_a, n_b))
    if next_queue:
        ct += 1
        queue = next_queue
    else:
        break

print(result_check(map_list, ct))

 

시간 복잡도

BFS로 모든 경로를 탐색 하므로 ( 이차형 시간 복잡도 )
해당 알고리즘 시간복잡도는 : 이차형 시간 복잡도 ( O(n**2) )