[Programmers][Python]합승 택시 요금

https://programmers.co.kr/learn/courses/30/lessons/72413

📌풀이

내가 쓴 풀이(성공)

• 플로이드-워셜 알고리즘 활용

from math import inf

#플로이드-워셜 알고리즘 활용

def solution(n, s, a, b, fares):
    answer = inf
    # 경로의 최소값을 저장하기 위한 리스트
    costs = [[inf]*n for _ in range(n)]
    
    # fares에서 불러온 경로값을 저장
    for c, d, f in fares :
        costs[c-1][d-1] = costs[d-1][c-1] = f
    
    for i in range(n):
        costs[i][i] = 0 # 본인에서 본인으로 가는 경로는 0
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 더 작은 값이 있는 경우, 이를 저장
                #costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])
                if costs[i][j] > costs[i][k] + costs[k][j] :
                    costs[i][j] = costs[i][k] + costs[k][j]
    
    # 다른 경로를 거쳐서 가는 방법 중 가장 작은 경우 확인
    for i in range(n):
        #answer = min(answer, costs[s-1][i] + costs[i][a-1] + costs[i][b-1])
        if answer > costs[s-1][i] + costs[i][a-1] + costs[i][b-1]: 
            answer = costs[s-1][i] + costs[i][a-1] + costs[i][b-1]
        
        
    return answer

📌후기

이전에 풀어볼 때는 다익스트라, 힙 구조를 활용하여 풀었었는데, 다른 사람들의 풀이 중 플로이드-워셜 알고리즘을 활용하여 해결한 경우가 있어 이를 적용하여 보았다. 다른 사람들의 풀이를 보면서 배워야 할 점이 상당히 많음을 다시 한 번 느낄 수 있었고, 코드를 구현하는 과정에서 min을 활용하는 것보다 if문을 활용하여 min 역할을 하게 하는 것이 시간적인 측면에서 더 효율적이라는 결과도 볼 수 있었다.

itertools의 product를 활용하는 알고리즘도 있었는데, 이 방법도 한번 찾아봐야겠다!