[2-4 숲속의기사]

고민해보았지만, 제 코드가 왜 시간초과 나는지 이유를 알 수 없어서, 답답한 마음에 질문드립니다.

[시간 복잡도]

- 각 좌표 정보 얻기 위한 이중포문 10^6

- visit 이차원 배열 2개 생성 2*10^3

- bfs1 10^6(최대)

- bfs2 10^6(최대)

- 총 3*10^6 + 2*10^3

- 위처럼 계산하면 시간 초과가 발생하지 않아야 하나, 발생하며

- 위에 적은 것에서 bfs2는 우선순위큐를 사용하기에 더더욱 연산횟수가 줄어들것이라 생각하였습니다.

왜 시간 초과가 발생한 걸까요ㅠ

import sys
input = sys.stdin.readline
from collections import deque
import heapq
d = [(0,1),(0,-1),(1,0),(-1,0)]

# 영희 시작점 -> 산딸기 전체 탐색
def bfs1():
    q = deque([(sx,sy)])
    visit1[sx][sy]=1
    while q:
        x,y = q.popleft()
        for dx,dy in d:
            nx = x + dx
            ny = y + dy
            if 0<=nx<N and 0<=ny<M and visit1[nx][ny]>visit1[x][y]+1 and arr[nx][ny]!=1:
                visit1[nx][ny]=visit1[x][y]+1
                q.append((nx,ny))

# 각 산딸기 -> 기사
# 우선순위큐를 활용, 어느 산딸기 위치에서 시작하든 최단 거리로 도달할 수 있도록
def bfs2():
    h = []
    for x,y in raspberry:
        heapq.heappush(h,(visit1[x][y]-1, x,y))
        visit2[x][y]=visit1[x][y]-1
    while h:
        dist, x, y = heapq.heappop(h)
        if visit2[x][y]<dist:
            continue
        if (x,y)==(ex,ey):
            return dist
        for dx,dy in d:
            nx,ny = x + dx,y+dy
            if 0<=nx<N and 0<=ny<M and arr[nx][ny]!=1 and visit2[nx][ny]>dist+1:
                visit2[nx][ny] = dist+1
                heapq.heappush(h,(dist+1,nx,ny))

# 입력
M,N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
sx,sy,ex,ey=0,0,0,0
raspberry = []
for i in range(N):
    for j in range(M):
        if arr[i][j]==2:
            sx,sy = i,j
        elif arr[i][j]==3:
            ex,ey = i,j
        elif arr[i][j]==4:
            raspberry.append((i,j))

visit1 = [[float('inf')]*M for _ in range(N)]
visit2 = [[float('inf')] * M for _ in range(N)]

bfs1()
print(bfs2())