S 지점에서 A,B 지점까지 도착하는데 소요되는 최소 비용을 구하는 문제이다.
처음에는 문제를 대충읽고 S->A->B
로 가는 비용과 S->B->A
로 가는 비용만 비교하면 되는줄 알았는데, 그게 아니라 S에서 출발해서 따로 따로 A, B로 가는데 경로가 중복되는 부분이 있다면 함께 갈 수 있으므로 비용이 한번만 계산되어야 하는... 그런 문제였다.
다익스트라 알고리즘을 사용하여 문제를 해결하려면 비용뿐 아니라 도착 지점까지의 경로도 함께 저장을 해주어야 중복되는 경로가 있을때 비용을 정확히 계산을 해줄수 있다.
이렇게 풀어주려고 하니 오히려 더 문제를 복잡하게 푸는것 같아 플로이드-워셜 알고리즘을 이용해 문제를 해결하였다.
먼저 모든 경로에 대해 최소비용을 구해주고, (S->C) + (C->A) + (C->B)
로 가는 비용을 더해주는 방식으로 구현하였다. (단, C는 A와B가 합승한 이후 하차하는 지점)
C가 어느 지점인지 모르기 때문에 1~n 까지 순회하면서 최소값을 찾아주는 방식으로 답을 찾아주었다.
INF = float('INF')
def solution(n, s, a, b, fares):
distance = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
for i in fares:
distance[i[0]][i[1]] = i[2]
distance[i[1]][i[0]] = i[2]
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
distance[i][j] = 0
elif distance[i][j] > distance[i][k] + distance[k][j]:
distance[i][j] = distance[i][k] + distance[k][j]
answer = INF
for i in range(1, n + 1):
answer = min(answer, distance[s][i] + distance[i][a] + distance[i][b])
return answer