[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

import heapq

INF = 987654321

def f(graph,s,n):
    dist = [INF]*(n+1)
    pq = [[0,s]]

    while pq:
        w,v = heapq.heappop(pq)

        if dist[v] != INF:
            continue
        
        dist[v] = w

        for nv,nw in graph[v]:
            if dist[nv] != INF:
                continue
            heapq.heappush(pq,[w+nw,nv])
    
    return dist

def solution(n, s, a, b, fares):
    graph = [[] for i in range(n+1)]
    
    for fare in fares:
        start,end,w = fare
        graph[start].append([end,w])
        graph[end].append([start,w])

    dist_s = f(graph,s,n)
    dist_a = f(graph,a,n)
    dist_b = f(graph,b,n)

    answer = 987654321
    for i in range(1,n+1):
        answer = min(answer,dist_s[i]+dist_a[i]+dist_b[i])

    return answer

풀이

A->i , S->i, B->i 의 합이 최소인 i 지점을 찾는 문제이다.

 

즉 S,A,B 를 시작점으로 하는 다익스트라를 3번하여 dist 목록을 구한다.

dist에는 출발지점에서 각 지점까지의 최단거리가 적혀있다.

 

dist의 인덱스 합을 통해  최단거리의 합의 최솟값을 구한다.

 

시간복잡도

다익스트라를 3번 사용했다 3* E*log(N) 이므로 O(E*log(N)) 이다.