[PG/Python] 합승 택시 요금

📌 문제

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

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

 

📌 문제 접근 방법

1. 다익스트라 알고리즘을 사용하여 풀이하였다.
2. 가장 중점이 되는 아이디어는 A와 B가 같이 택시를 타고 가는 지점이 k라고 했을 때,
   택시 요금은 시작지점부터 k까지의 요금(s~k) + k부터 A의 집까지 요금(k~a) + k부터 B의 집까지 요금(k~b) 와 같다는 것이다.
3. 다익스트라 알고리즘을 사용하여 각 구간의 요금을 계산해주었는데, 이미 앞의 구간에서 지나온 지점은 다시 지나지 않아야 최소 요금이 되기 때문에 이를 생각해주어야 했다.
   temp에 목표지점까지 지나온 경로를 모두 저장하여 다익스트라 함수를 시작할 때 모두 방문처리 해줬다.

 

📌 코드

def solution(n, s, a, b, fares):
    def dijkstra(start, end):
        nonlocal temp
        
        visited = [0 for _ in range(n+1)]
        for t in temp:
            visited[t] = 1
        
        way = {start : [start]}
        
        dist = [float('inf') for _ in range(n+1)]
        dist[start] = 0
        
        for _ in range(n+1):
            min_idx = -1
            min_value = float('inf')
            
            for i in range(1, n+1):
                if not visited[i] and dist[i] < min_value:
                    min_idx = i
                    min_value = dist[i]
            
            if min_idx == end:
                return min_value
            
            visited[min_idx] = 1
            
            for j, d in graph[min_idx]:
                if dist[j] > dist[min_idx]+d:
                    dist[j] = dist[min_idx]+d
                    way[j] = way[min_idx] + [j]
                
        return 999999
            
                
    graph = [[] for _ in range(n+1)]
    for fare in fares:
        graph[fare[0]].append((fare[1], fare[2]))
        graph[fare[1]].append((fare[0], fare[2]))
    
    answer = float('inf')
    for k in range(1, n+1):          
        temp = []
        cost = dijkstra(s, k) + dijkstra(k, a) +dijkstra(k, b)
        answer = min(answer, cost)
        
    return answer