문제의 핵심 풀이는 택시를 합승해서 내리는 위치를 k라고 할 때, 택시 요금은 아래와 같이 정의할 수 있다.
f(s,a,b,k) = fare(s, k) + fare(k, a) + fare(k, b)
이 때 k는 합승을 마치고 각자 택시를 타는 지점이고, fare(v,w)는 정점 v와 w의 최저 택시 요금이다.
함수 f를 최소로 만드는 값은, 다른 값은 고정이므로 f를 최소로 만드는 k값을 찾는것이다.
각 fare의 항목에 들어가는 함수 값은 k에 따라 값이 변화하므로 모든 가능한 k 값에 대한 fare 항목들의 최솟값을 구해야한다
따라서 각 지점으로부터 각 지점으로까지의 최소 거리를 구하는 알고리즘인 floyd-warshall algorithm을 사용하였다.
def solution(n, s, a, b, fares):
# 최댓값에 대한 가정, 요금 f의 범위가 [1, 100,000]이고,
# 징점의 개수는 최대 200이기 때문에 가능한 최댓값은 19,900,000이지만 넉넉하게 잡았다.
INF = 100000000
# make adjacency matrix
distance = [[INF for _ in range(n)] for _ in range(n)]
# initialize weights for line to itself
for i in range(n):
distance[i][i] = 0
for i, j, weight in fares:
distance[i-1][j-1] = weight
distance[j-1][i-1] = weight # 양방향 그래프이므로 반대 방향으로도 간선을 놓는다.
#floyd-warshall algorithm
def floyd_warshall(G):
for k in range(n): # 중간노드 k에 대해서
for i in range(n): # 시작노드 i에 대해서
for j in range(n): # 끝노드 j에 대해서
G[i][j] = min(G[i][j], G[i][k]+G[k][j])
floyd_warshall(distance) # 요금에 대한 인접 행렬을 가지고 floyd-warshall 알고리즘
# 그리고 중계점 k에 대해 가능한 모든 경우에서 가장 작은 값을 구한다.
answer = min([distance[s-1][k]+distance[k][a-1]+distance[k][b-1] for k in range(n)])
return answer