from itertools import product
def solution(n, s, a, b, fares):
s, a, b = s - 1, a - 1, b - 1
DP = [[100000000] * n for _ in range(n)]
for v1, v2, cost in fares:
DP[v1 - 1][v2 - 1] = DP[v2 - 1][v1 - 1] = cost
for t in range(n):
DP[t][t] = 0
for via, i, j in product(range(n), repeat=3):
if DP[i][j] > (l := DP[i][via] + DP[via][j]):
DP[i][j] = l
return min(DP[s][k] + DP[k][a] + DP[k][b] for k in range(n))
난 항상 문제풀고 다른사람들의 풀이 대략 3페이지까지 훑어보는데, 윤응구 이사람 코딩스타일이 나랑 비슷한데 실력이 더 좋다. 딱 보고 오 좀치네? 하고 이름보면 윤응구 이사람인 경우가 꽤 많았다. 이것도 이사람 코드임
풀이
v1에서v2까지 최단 경로를 다익스트라 알고리즘으로 구한다.
0번 지점부터n-1지점까지 동승해서 가는 모든 비용중 최소값을return
Floyd-Warshall Algorithm
DP[i][j] 는 i에서 j로 가는 비용을 의미한다. 이 비용을 최소값으로 업데이트 해주는 알고리즘이 Floyd-Warshall Algorithm다.
1 \(\rightarrow\)2는 30이다. 하지만 최단경로는 아니다. DP[1][2]의 최단경로는
DP[1][2] = min(DP[1][2], DP[1][3] + DP[3][2])
이렇게 구해주어야한다. 조금더 일반화를 시키면
DP[i][j] = min(DP[i][j], DP[i][via] + DP[via][j])
via= 모든vertex
그래서 1번 예제의 그래프를 Floyd-Warshall Algorithm 을이용해 최단거리 비용을 갱신한다면
이 DP표를 이용해서
DP[출발지][동승지점] + DP[동승지점][a의 도착점] + DP[동승지점][b의 도착점]
동승지점 = [0, 1, 2, ... n]
최소비용을 구해주면 된다.
의문점
다른사람 코드를 공부해서 이해하는거다보니 의문점이 하나 생기는데
via, i, j in product(range(n), repeat=3)
이부분 via, i, j 를 i, j, via 로 바꾸면 통과가 안된다. 어차피 최소비용을 구해나가는 문제라 i, j를 고정시켜놓고 경유지를 바꿔가며 최소값을 구하는거랑 via 를 고정시켜놓고 최소값을 구해가는거랑 똑같을꺼라 생각이 들지만 틀리더라… 이유를 모르겠다.
그리고 최소값갱신하는 부분에서
min(DP[i][j], DP[i][via]+DP[via][j]) # 시간초과남
#
#
#
if DP[i][j] > (l := DP[i][via] + DP[via][j]):
DP[i][j] = l
이걸로 보았을 때, 연산 시간이 if 보다 배열 indexing 훨씬 많이 잡아먹는다는것을 알 수 있음