시간 초과 코드

아기 상어 문제 코드 비교해서 시간 복잡도 분석하기

import sys
import heapq
from collections import deque
input = sys.stdin.readline
tmp, get  = 0, 0
final = 0
n, m = map(int, input().split())
p = []
for y in range(n):
    arr = list(map(str, input().rstrip()))
    if tmp == 0:
        for x in range(m):
            if arr[x] == 'S':
                start = (y, x, 0)
                flg = 1
    p.append(arr)
def bfs(start, p):
    global get
    global final
    que = deque()
    que.append(start)
    y, x, time = start
    dirs = [(0,1), (0,-1), (1,0), (-1,0)]
    min_time = []
    visited = set()
    while que:
        for sr, sc in dirs: #좌표 이동
            dr = y+sr #좌표 이동
            dc = x+sc
            if 0 <= dr < m and 0 <= dc < n: #지나갈 수 있는 구역
                if p[dc][dr] != 'D':
                    que.append((dr, dc, time + 1))
                    heapq.heappush(min_time, (time+1, dr, dc))
                    if p[dc][dr] == 'F':
                        get = 1 #물고기 서식지에 도착
                    if get == 1 and p[dc][dr] == 'H': #도착
                        final = 1
        if min_time:
            return final, min_time[0]
        else: return None, None
sec = 0
while True:
    final, nv = bfs(start, p)
    if nv is None:
        sec = -1
        break
    time, dr, dc = nv
    sec += time
    start = (dr, dc, 0)
    if final == 1: break
print(sec)