택시 합승 요금

택시 합승 요금 문제 바로가기

풀이

그래프의 최단 거리 문제

플로이드 와샬 알고리즘 을 이용해서 최단거리 구하기.

1. 모든 정점에서 정점으로 가능 최단거리 를 저장하는 list 설정
   (처음 초기화는 가장 큰 값)
2. 방향에 따른 거리 변화 가 없고, 자기 자신에게 가는 비용 은 0 으로 초기화
   ( list[i][j] == list[j][i] )
3. 두가지 목적지로의 최단거리를 구하면 된다.
   ( 예) 출발점 : 4, 도착지점a : 6, 도착지점b : 2 이라면, )

4 -> ? ->6 와 4 -> ? ->2 의 거리를 더하면 끝

풀이 코드

def solution(n, s, a, b, fares):
	# 정수의 최댓값 담을 변수
	inf = float('inf')    
    
    	# 모든 정점으로부터 정점까지의 최소 비용 list 초기화
    graph = [[inf] * n for _ in range(n)]
    
	# 자기 자신 가는 비용은 0
    for i in range(n):                     
        graph[i][i] = 0
	
    # 방향성이 없는 그래프니까 1 -> 4 , 4 -> 1 의 비용은 같음 
    for i in fares:
        graph[i[0] - 1][i[1] - 1] = i[2]   
        graph[i[1] - 1][i[0] - 1] = i[2]			

	# 1 -> 4 라고 가정, 직선거리가 가까운지 경유한게 가까운지 비교후 가까운 값을 List에 저장
    for t in range(n):
        for i in range(n):
            for j in range(i+1, n):                                 #최소 비용 계산
                temp = min(graph[i][j], graph[i][t] + graph[t][j]) 
                graph[i][j] = graph[j][i] = temp

    answer = inf
    # 공통으로 이동한 비용 + 공통 이동지점으로부터 각각의 목적지까지의 비용중 가장 작은 비용!
    for t in range(n):                              #경유점에 따라 최소 합승 비용 탐색
        temp = graph[s - 1][t] + graph[t][b - 1] + graph[t][a - 1]      
        answer = min(answer, temp)

    return answer