[알고리즘] 합승 택시 요금

프로그래머스 2021 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제
합승 택시 요금 문제

---

1.플로이드 와샬 알고리즘

table[i][j] = min(table[i][j],table[i][k]+table[k][j])

플로이드 와샬 알고리즘을 활용하여 각 노드로 가는 최소값을 찾아준다.

---

2.요금 계산

(같이 합승해서 간 요금) + (A가 따로가는 거리) + (B가 따로가는 거리)

노드의 개수만큼 계산하여 최소값을 찾는다.
시작이 1이고 A는 3, B는 4로 이동한다고 하였을때, 1에서 2까지 합승으로 이동하고 2에서 3, 2에서 4로 이동하는 요금을 더하는 방식으로 진행하면 계산이 된다.
처음부터 따로가는 부분은 시작하는 노드에서 출발하는 경우가 된다. 1에서 1로 합승(처음부터 합승을 하지 않는다), 1에서 3, 1에서 4로 이동하는 요금이면 따로 출발하는 요금이 된다.

3.테이블과 답 초기화

테이블과 답을 초기화 할 때 가장 큰 수로 초기화를 하기위해 처음에는 문제에 주어진 간선의 최대 값을 사용했지만 그 조차도 더 큰 수가 들어오는 문제인지 오답이 나왔다. 그래서 무한 inf를 사용하여 값을 초기화하였다.

---

코드

def solution(n, s, a, b, fares):
    table = [[float('inf')]*n for _ in range(n)] # ③
    for i in range(n): table[i][i] = 0
    for i in fares: 
        table[i[0]-1][i[1]-1],table[i[1]-1][i[0]-1] = i[2],i[2]
    for k in range(n): # ①
        for i in range(n):
            for j in range(n):
                table[i][j] = min(table[i][j],table[i][k]+table[k][j])
    answer = float('inf') # ③
    for i in range(n): # ②
    	answer = min(answer, table[s-1][i]+table[i][a-1]+table[i][b-1])    
    return answer