[프로그래머스, 파이썬] 부대복귀 - 레벨 3 | 다익스트라 알고리즘

📌 프로그래머스 Level 3 : 부대복귀

특정 노드까지 최단 거리를 구하는 문제!

즉 다익스트라 알고리즘 을 활용하는 문제이다.

📝 내 답안

from collections import defaultdict,deque
def solution(n, roads, sources, destination):
    answer = [-1 for _ in range(len(sources))]
    M = 100001*n
    graph = defaultdict(list)
    # destination까지 최단거리 리스트
    dis = [M for _ in range(n+1)]
    for a,b in roads:
        graph[a].append(b)
        graph[b].append(a)
    
    q = deque()
    q.append((destination,0))
    while q:
        s,cost = q.popleft()
        for next in graph[s]:
            if next == destination:
                dis[next] = 0
            if cost+1 < dis[next]:
                dis[next] = cost+1
                q.append((next,cost+1))
                
    for i in range(len(sources)):
        s1 = sources[i]
        if dis[s1] == M:
            continue
        answer[i] = dis[s1]
    return answer

실행결과

정확성 테스트
테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.02ms, 10.2MB)
테스트 4 〉 통과 (0.01ms, 10.1MB)
테스트 5 〉 통과 (0.02ms, 10.2MB)
테스트 6 〉 통과 (17.58ms, 16.3MB)
테스트 7 〉 통과 (20.98ms, 17.4MB)
테스트 8 〉 통과 (29.32ms, 21.9MB)
테스트 9 〉 통과 (10.44ms, 13.9MB)
테스트 10 〉 통과 (11.44ms, 14.5MB)
테스트 11 〉 통과 (694.85ms, 117MB)
테스트 12 〉 통과 (587.64ms, 117MB)
테스트 13 〉 통과 (690.80ms, 117MB)
테스트 14 〉 통과 (763.74ms, 117MB)
테스트 15 〉 통과 (601.35ms, 117MB)
테스트 16 〉 통과 (173.44ms, 43.7MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0