인프런 커뮤니티 질문&답변

import sys
from collections import deque
sys.stdin = open("input.text",  "rt")
input = sys.stdin.readline

n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = mat[0][0]
que = deque()
que.append((0, 0))

while que:
    y, x = que.popleft()
    for dy, dx in zip([0, 1], [1, 0]):
        ny, nx = y+dy, x+dx
        if 0 <= ny < n and 0 <= nx < n:  # 범위 확인
            if dp[y][x]+mat[ny][nx] < dp[ny][nx]:  # 최소 에너지가 존재하는 경우
                dp[ny][nx] = dp[y][x]+mat[ny][nx]
                que.append((ny, nx))
            elif not dp[ny][nx]:  # 처음 초기화되어 있는 곳(0)
                dp[ny][nx] = dp[y][x]+mat[ny][nx]
                que.append((ny, nx))
print(dp[n-1][n-1])

이 문제를 bfs 방식으로 풀었을 때 시간 복잡도의 큰 손해가 존재하는지 궁금합니다. 테스트케이스는 통과를 하였습니다.