[파이썬] 배달- Summer/Winter Coding(~2018) [CODING TEST #63]

https://school.programmers.co.kr/learn/courses/30/lessons/12978

 

 

하나의 노드에서 다른 노드들로의 최단 거리를 구하는 문제이므로 다익스트라를 이용했다.

양방향이므로 거리 정보가 입력될 때 a -> b, b -> a로의 길이를 함께 기록했다.

그리고 최소 힙을 활용한 우선순위 큐를 이용하여 다익스트라를 구현했다.

 

A와 B 사이에는 여러 도로가 존재할 수 있기 때문에 처음에는 A와 B 사이에 town 리스트 정보를 생성할 때 가장 짧은 도로 정보만 넣으려 했는데, 어차피 다익스트라는 해당 노드와 인접한 모든 노드를 확인한다. town[node]를 모두 확인하여 가장 짧은 도로 정보를 이용해 갱신되므로 굳이 긴 코드를 짤 필요가 없었다.

 

다익스트라 상당히 어렵다. 더 풀어봐야지..

 

import heapq
def solution(N, road, K):
    answer = 0
    INF = 987654321
    town = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    for data in road: # data[0] : start / data[1] : end / data[2] : dist
        town[data[0]].append((data[2],data[1]))
        town[data[1]].append((data[2],data[0]))
    
    q = [] # heapq 생성
    heapq.heappush(q,(0,1)) # 시작 지점 push
    distance[1]=0 # 시작 지점의 길이는 0
    while q:
        dist, node = heapq.heappop(q) 
        if distance[node] < dist: # distance 리스트보다 길면 무시
            continue
        for d, n in town[node]:
            if dist + d < distance[n]: # 최단 거리 갱신
                distance[n] = dist + d
                heapq.heappush(q,(dist + d,n)) # 갱신된 길이를 push. 가장 작은 값은 heapq의 맨 앞으로 옴
    
    return len([final for final in distance if final <= K])