[프로그래머스] Lv.3 합승 택시 요금 [Python, 파이썬] KAKAO

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/72413
• 🔑 다익스트라
  • 1번 풀이 : 모든 노드를 시작점으로 n번의 다익스트라를 호출
    
    • n → s  +  n → a  +  n → b 비용의 최솟값을 찾는다.
    • 최대 n이 200이므로 굉장히 느림 (최대 200번의 다익스트라 호출), 최대 14677.97ms
  • 2번 풀이 : s, a, b를 시작 지점으로 총 3번의 다익스트라 호출
    • s → n  +  a → n  +  b → n 비용의 최솟값을 찾는다.
    • n이 몇이든 다익스트라는 3번만 호출하면 되기 때문에 굉장히 빠름, 최대 230.38ms

 

---

모든 노드를 시작점으로 n번의 다익스트라 호출

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph, n, start):      # 다익스트라(그래프, 지점개수, 출발지점)
    cost = [int(1e9)] * (n+1)
    cost[start] = 0
    q = []
    heappush(q, (0, start))
    
    while q:
        now_cost, now_node = heappop(q)
        
        if now_cost > cost[now_node]:
            continue
        
        for next_cost, next_node in graph[now_node]:
            new_cost = next_cost + cost[now_node]
            if cost[next_node] > new_cost:
                cost[next_node] = new_cost
                q.append((new_cost, next_node))
    return cost

# 지점의 개수 n, 출발지점 s, A의 도착지점 a, B의 도착지점 b, 지점 사이의 예상 택시요금을 나타내는 fares
def solution(n, s, a, b, fares):
    answer = int(1e9)
    graph = defaultdict(list)
    
    for f in fares:                         # 양방향 그래프 생성
        graph[f[0]].append((f[2], f[1]))
        graph[f[1]].append((f[2], f[0]))

    for start in range(1, n + 1):               # 모든 지점에서 출발을 해본다.
        cost = dijkstra(graph, n, start)        # start 지점을 출발지로 한 최소 비용 리스트 반환
        answer = min(answer, cost[s] + cost[a] + cost[b])
        # start -> s, start -> a, start -> b 의 비용 최솟값을 찾음
    
    return answer

 

---

s, a, b를 시작 지점으로 총 3번의 다익스트라 호출

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph, n, start):      # 다익스트라(그래프, 지점개수, 출발지점)
    cost = [int(1e9)] * (n+1)
    cost[start] = 0
    q = []
    heappush(q, (0, start))
    
    while q:
        now_cost, now_node = heappop(q)
        
        if now_cost > cost[now_node]:
            continue
        
        for next_cost, next_node in graph[now_node]:
            new_cost = next_cost + cost[now_node]
            if cost[next_node] > new_cost:
                cost[next_node] = new_cost
                q.append((new_cost, next_node))

    return cost

# 지점의 개수 n, 출발지점 s, A의 도착지점 a, B의 도착지점 b, 지점 사이의 예상 택시요금을 나타내는 fares
def solution(n, s, a, b, fares):
    answer = int(1e9)
    graph = defaultdict(list)
    
    for f in fares:                         # 양방향 그래프 생성
        graph[f[0]].append((f[2], f[1]))
        graph[f[1]].append((f[2], f[0]))

    cost_s = dijkstra(graph, n, s)          # s를 시작 위치로 하는 다익스트라
    cost_a = dijkstra(graph, n, a)          # a를 시작 위치로 하는 다익스트라
    cost_b = dijkstra(graph, n, b)          # b를 시작 위치로 하는 다익스트라

    for i in range(1, n+1):                 # 가장 비용이 적은 중간 지점을 찾는다.(합승 끝나는 지점)
        answer = min(answer, cost_s[i] + cost_a[i] + cost_b[i])
    
    return answer