📌 프로그래머스 - 합승 택시 요금

다익스트라 + 완전탐색으로 풀었다.

처음에는 문제보고 어떻게 풀지 생각이 많았는데.. 잘 정리해서 풀어보니 꽤 풀만했다!

효율성 완전 간신히 통과했는데, 구글링해보니 플로이드-워셜로 푸는게 정석 같다.

📝내 답안

from collections import defaultdict,deque
def solution(n, s, a, b, fares):
    answer = n * 100001
    M = n * 100001
    
    # 최단거리 배열 return 다익스트라
    # graph[시작] = [끝,거리]
    def dij(start,graph):
        dis = [M for _ in range(n+1)]
        dis[start] = 0
        q = deque()
        q.append((start,0))
        
        while q:
            now,cost = q.popleft()
            for next,c in graph[now]:
                if c+cost < dis[next]:
                    dis[next] = c+cost
                    q.append((next,c+cost))
        return dis
    
    graph = defaultdict(list)
    for i,j,c in fares:
        graph[i].append([j,c])
        graph[j].append([i,c])
    
    dis1 = dij(s,graph)
    
    # 완전탐색 : 최단거리를 가지는 i 지점 찾기
    for i in range(n+1):
        # i지점부터 모든 지점까지 최단경로 저장
        dis2 = dij(i,graph)
        if dis1[i]+dis2[a]+dis2[b] < answer:
            answer = dis1[i]+dis2[a]+dis2[b]
        
    return answer

🔮 풀이

답안에 사용한 알고리즘은 다음과 같다.

1. 특정 지점부터 모든 지점까지의 최단거리 저장하는 함수 만들기.
   def dij(start,graph): ~~~

2. graph 작성.
   graph[노드1] = [노드2, 거리]

3. 출발지점(s)부터 각 모든 지점까지의 최단거리를 저장한 dis1 = dij(s,graph)

4. 합승지점을 1에서부터 n까지 지정해보면서, 가장 최단 거리를 가지는 값을 answer에 갱신하기.(완전탐색)

    # 완전탐색 : 최단거리를 가지는 i 지점 찾기
    for i in range(n+1):
        # i지점부터 모든 지점까지 최단경로 저장
        dis2 = dij(i,graph)
        if dis1[i]+dis2[a]+dis2[b] < answer:
            answer = dis1[i]+dis2[a]+dis2[b]