합승 택시 요금

문제

---

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

코딩테스트 연습 - 합승 택시 요금

 

나의 풀이

---

플로이드 와샬 알고리즘을 사용해 중간에 k 지점을 통과할 때 비용을 계산한다. (플로이드 와샬 알고리즘이란 다익스트라와 같이 최소 비용을 계산하는 알고리즘 중 하나이지만, 거점 k를 거쳐가는 경우를 기준으로 계산한다.) x->y 비용을 c(x,y)로 나타낸다고 하면, 모든 거점 k에 대해 c(출발지점, k) + c(k, A의 도착지점) + c(k, B의 도착지점)을 계산해 최솟값을 찾아내면 된다. 말로 풀어 설명하자면 k까지 같이 합승하고 k지점부터 A와 B가 각각 따로 가는 비용인 셈이다. 그런데 방향성이 없는 그래프이므로 c(x,y)==c(y,x)이다. 따라서 아래 그래프에서 보면 결국 대각선 위쪽 부분만 비용을 계산해주면 된다.

코드

---

def solution(n, s, a, b, fares):
    INF = int(1e9)  #무한을 의미하는 값 10억 설정
    graph = [[INF]*n for _ in range(n)]
    
    for i in range(n):
        graph[i][i] = 0 # 자기 자신에게 가는 값 0
    for x,y,f in fares:
        graph[x-1][y-1] = graph[y-1][x-1] = f
    
    for k in range(n):
        for i in range(n):
            for j in range(i+1,n):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
                graph[j][i] = graph[i][j]
    answer = INF
    for k in range(n):
        answer = min(answer, graph[s-1][k]+graph[k][a-1]+graph[k][b-1])
    

    return answer