프로그래머스 / 합승 택시 요금 / python

def solution(n, s, a, b, fares):
    answer = 0
    dist = [[1e9] * (n+1) for _ in range(n+1)]
    for fare in fares:
        i, j, c = fare
        dist[i][j] = min(dist[i][j], c)
        dist[j][i] = min(dist[j][i], c)
        
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i != j:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                if i==j:
                    dist[i][j] = 0

    answer = 1e9
    for i in range(1, n+1):
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b])
    return answer

플로이드 와샬 알고리즘 문제
다익스트라로도 해결할 수 있을 것 같지만 이 문제처럼 모든 노드들에 대해서 서로의 최소 경로를 구해야하는 문제의 경우는 다익스트라를 n 번 하는것 보다는 플로이드 와샬 알고리즘으로 구하는 것이 적합하다.( 플로이드 와샬 알고리즘의 경우 시간 복잡도가 O(n^3)이다.

플로이드 와샬 알고리즘을 통해 각 노드들에 대해서 거리를 모두 구했다면 이제 for문을 통해 최소값을 정답으로 구하면 된다.

---

플로이드 와샬 알고리즘을 바로 떠올렸지만 최소 값을 구하는 과정에서 많이 해맸다. 저렇게 for문을 통해 구할 수 있는 거는 떠올리지 모르고 최소값을 탐색하는 안 좋은 방법으로 시도 했었다가 시간 초과가 나왔다.

#     while True:
#         d_cost = min(dist[s])
#         idx = dist[s].index(d_cost)
        
#         a_cost = dist[s][a]
#         b_cost = dist[s][b]
        
#         if s == a:
#             print(idx, a)
#             answer += b_cost
#             break
#         if s == b:
#             answer += a_cost
#             break
            
#         if a_cost < dist[idx][a] or b_cost < dist[idx][b]:
#             answer += a_cost
#             answer += b_cost
#             break
#         answer += d_cost
#         dist[idx][s] = 1e9
#         s = idx

위 코드처럼 기껏 플로이드 와샬 알고리즘을 통해 모든 거리를 구했지만... 다시 한 번 탐색하는 방법....