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

import heapq



def solution(N, road, K):

    n_road = [500001] * (N+1)

    n_road[1] = 0

    sorted_road = [[] for i in range(N+1)]

    for road_num in road:

        sorted_road[road_num[0]].append([road_num[2], road_num[1]])

        sorted_road[road_num[1]].append([road_num[2], road_num[0]])

    # print(sorted_road)

    

    q = []

    heapq.heappush(q, [0, 1])

    while q:

        cur_node = q.pop()

        for dist, b in sorted_road[cur_node[1]]:

            if dist + n_road[cur_node[1]] < n_road[b]:     # 1에서 cur로, cur에서 b로, 1에서 b로

                n_road[b] = dist + n_road[cur_node[1]]

                q.append([n_road[b], b])

    return len(list(filter(lambda x: x <=K, n_road)))

다익스트라 알고리즘을 구현하는데 의문점이 생겨서 여기 질문을 남깁니다.

1. 다익스트라 알고리즘에서 인접한 거리의 노드를 선택하기 위해서 heap 자료구조를 사용하는데 꼭 인접한 거리의 노드를 선택해야할 이유가 있을까요? 제가 원래 heap을 사용했던 python 코드를 단순히 배열로 바꿔서 가장 인접한 거리의 노드부터 선택하지 않음에도 불구하고 작동이 잘 되어서 질문을 남깁니다.

- 제가 구현한 코드에서는 인접한 거리를 방문하든 안하든 결국 모든 노드들을 방문하여서 차이가 없다고 생각되었습니다.

2. 위와 같은 방법의 시간 복잡도는 어떻게 되는것인가요? 아직 시간복잡도 계산이 미숙해서 그런지 잘 모르겠습니다.