[Python] 프로그래머스 합승 택시 요금

 

 

 

 

 

문제에 대한 자세한 설명은 아래 링크 참조

 

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

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

 

 

Dijkstra 알고리즘을 사용해서 풀었다. (최단거리 알고리즘 사용해야함)

이것 때문에 쓴 Dijkstra 알고리즘 설명 글 -> 990427.tistory.com/50

[Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘

 

택시를 언제 내릴지 모르니까 1부터 n까지를 시작점으로 두고 최단경로를 따져봐야한다.

(1->s)+(1->a)+(1->b) 이 세 경로의 합이 s에서 1까지 합승하고, 1부터 A,B까지 따로가는 경우이다.

 

처음부터 따로가는 경우, s에서 n까지 합승 후 따로가는 경우를 나누어 다익스트라 해야한다.

 

Code

from collections import defaultdict
import heapq

def dijkstra(n,l,r):
    cost=[float('inf') for x in range(n+1)]
    h=[(0,l)]
    cost[l]=0
    
    while h:
        cnt,num=heapq.heappop(h)
        if cost[num]<cnt:
            continue
            
        for i,j in dic[num]:
            if cnt+j<cost[i]:
                cost[i]=cnt+j
                heapq.heappush(h,(cnt+j,i))
                
    return cost[r]


def solution(n, s, a, b, fares):
    global dic
    dic=defaultdict(list)
    for x,y,z in fares:
        dic[x].append([y,z])
        dic[y].append([x,z])
        
    #s->a, s->b 따로가는 경우
    res=dijkstra(n,s,a)+dijkstra(n,s,b)
    
    for i in range(1,n+1):
        if i==s:
            continue
        # s->i 까지 합승 후 i에서 부터 따로가는 경우 
        res=min(res,dijkstra(n,s,i)+dijkstra(n,i,a)+dijkstra(n,i,b))
        
    return res