코딩 테스트(Python) 2021 KAKAO BLIND RECRUITMENT 합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413?language=python3

프로그래머스

import heapq  # Dijkstra 알고리즘을 구현하기 위해 우선순위 큐를 사용
import sys  # 무한대(INF) 값을 사용하기 위해 sys 모듈 임포트

def solution(n, s, a, b, fares):
    INF = sys.maxsize  # 무한대 값을 설정하여 초기 거리 계산에 사용
    answer = INF  # 최소 요금을 저장할 변수, 초기값은 INF로 설정
    graph = [[] for _ in range(n + 1)]  # 그래프를 저장할 리스트

    # 그래프에 요금 정보를 추가 (양방향 그래프)
    for f in fares:
        node1, node2, fee = f
        graph[node1].append((node2, fee))
        graph[node2].append((node1, fee))

    # 다익스트라 알고리즘을 사용하여 특정 시작점에서 모든 노드까지의 최단 거리 계산
    def dijkstra(s):
        q = []  # 우선순위 큐
        distance = [INF] * (n + 1)  # 각 노드까지의 최단 거리를 저장, 초기값은 INF
        heapq.heappush(q, (0, s))  # 시작점의 거리와 노드를 큐에 추가
        distance[s] = 0  # 시작점에서 시작점까지의 거리는 0

        while q:  # 큐가 빌 때까지 반복
            dist, now = heapq.heappop(q)  # 가장 짧은 거리의 노드를 꺼냄
            if distance[now] < dist:  # 이미 처리된 노드면 무시
                continue
                
            # 현재 노드와 연결된 인접 노드 탐색
            for g in graph[now]:
                cost = dist + g[1]  # 현재 노드를 거쳐 인접 노드로 가는 거리 계산
                if cost < distance[g[0]]:  # 계산된 거리가 기존 거리보다 짧으면 갱신
                    distance[g[0]] = cost
                    heapq.heappush(q, (cost, g[0]))  # 큐에 새로운 거리와 노드를 추가
        return distance

    # 모든 노드에 대해 다익스트라 실행 결과를 저장
    distance_list = [[]] + [dijkstra(i) for i in range(1, n + 1)]

    # 공유 택시를 사용할 각 노드에 대해 최소 요금 계산
    for i in range(1, n + 1):
        # 시작점 -> i -> A, B로 가는 비용을 계산하여 최소값 갱신
        answer = min(distance_list[s][i] + distance_list[i][a] + distance_list[i][b], answer)

    return answer  # 최소 택시 요금 반환