[프로그래머스] 배달

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

코딩테스트 연습 - 배달

 

다익스트라 알고리즘을 이용하여 1 에서 출발하여 각 도착하는 번호에 대한 최단 시간을 구하면 된다.

1 에서 출발하여 도작하는 번호의 시간을 계속 비교하면서 더 적은 시간을 distances 에 넣어주면 된다. distances[b] 가 0 인 것은 c 가 1 이상이므로 처음 지나는 경로라는 뜻으로 b 를 queue 에 값을 넣어준다.

모든 도로가 이어져 있으므로 각 번호의 distances 의 값은 존재하며, 방문했던 경로는 시간이 길어지므로 queue 에 넣지 않는다. 

 

from collections import defaultdict, deque

def solution(N, road, K):
    answer = 0
    dic = defaultdict(list)
    
    for i in road:
        a, b, c = i
        dic[a].append([b, c])
        dic[b].append([a, c])
    
    queue = deque([1])
    distances = defaultdict(int)
    
    while queue:
        a = queue.popleft()
        
        for b, c in dic[a]:
            if distances[b] > distances[a] + c or distances[b] == 0:
                distances[b] = distances[a] + c
                queue.append(b)
    
    for key in distances.keys():
        if distances[key] <= K or key == 1:
            answer = answer + 1
    
    return answer

print(solution(5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3)) # 4