cj98123   11달 전

고수 선생님들께 여쭤봅니다.

이런 2차원 dp 최단거리 문제에서

왜 heapq 를 사용하는 djikstra 보다 deque를 사용하는 BFS + 가지치기가 더 빠른건가요?

heapq TLE : 100846469

deque pass : 100847464

몇몇 문제들에서 비슷한 상황을 겪었는데 이해가 잘 안되어서요.ㅜㅜ

wnwoghd22   11달 전

시간복잡도 자체가 다르게 계산되니까요

댓글을 작성하려면 로그인해야 합니다.