합승 택시 요금

문제 설명

S의 시작점에서 A의 도착점 과 B의 도착점의 최단경로를 구하는문제

 

 

문제 풀이

• 해당 문제는 최단 경로를 찾는 문제이기 때문에 다익스트라 알고리즘으로 풀 수 있다.
• 다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.
• 이 과정에서 도착 정점 뿐아니라 모든 정점까지 최단경로로 방문하며 각 정점까지의 최단경로를 찾게된다.

최소비용을 구하는 그래프 알고리즘

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 프로이드 워샬 알고리즘

 

동작 단계

1. 출발 노드와 도착노드를 설정
2. 최단거리 테이블 초기화
3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고 방문하지 않은 노드 중  거리가 가장 짧은 노드를 선택 후 방문처리
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트
5. 3~4의 과정 반복

문제 해결 코드

import heapq
INF = 10000000
def dijkstra(n,graph,s) :
    q = []       #힙큐 사용
    distance = [INF] * (n+1)	# 최단 거리 테이블
    heapq.heappush(q,(0,s))		# 시작점과 가중치 0 입력
    while q :					# q의 값이 잇는 동안 반복
        dist, now = heapq.heappop(q)	# 가중치, 현재 노드 
        if distance[now] < dist :		# 최단거리 테이블의 현재 노드의 가중치와 현재 노드의 가중치 비교
            continue
        for  next_node,fee in graph[now] :	#다음 노드,간선 가중치 가져옴
            cost = dist + fee				# 현재 노드까지의 가중치 + 다음 노드의 가중치
            if distance[next_node] > cost :	#최단거리 테이블의 가중치와 비교
                distance[next_node] = cost	# 변경
                heapq.heappush(q,(cost,next_node))	# 코스트 및 다음노드의 값 q에 추가
    return distance
            
def solution(n,s,a,b,fares):
    answer = 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])

    a_list = dijkstra(n,graph,s)
    b_list = dijkstra(n,graph,a)
    c_list = dijkstra(n,graph,b)
    for i in range(n+1) :
        total_list = a_list[i] + b_list[i] + c_list[i]
        answer = min(answer,total_list)
    return answer