[Programmers] Level 3. 합승 택시 요금

🔗 Problem Link

프로그래머스

---

❔Thinking

• A,B 두 사람이 S지점에서 출발하여 각자의 집 C,D로 가는 택시 합승 최소 비용을 반환한다. (합승하지 않을 수 있다.)

---

💻Solution

def solution(n, s, a, b, fares):
    INF = int(1e9)
    answer = INF
    # 2차원 그래프 생성
    graph = [[INF] * (n+1) for i in range(n+1)]
    # 그래프 초기화
    for i in range(1,n+1):
        for j in range(1, n+1):
            if i == j:
                graph[i][j] = 0
    # 요금표 입력
    for data in fares:
        c, d, cost = data[0], data[1], data[2]
        graph[c][d] = cost
        graph[d][c] = cost

    # 플로이드워셜 알고리즘
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    # 최소 비용 계산
    for k in range(1, n+1):
        fare = graph[s][k] + graph[k][a] + graph[k][b]
        if fare < answer:
            answer = fare
    return answer

---

🗝️keypoint

1. 합승하여 반드시 C나 D에 도착할 필요 없이, 중간에 내려 각자가 택시를 이용할 수 있다.
2. 합승하지 않을 수 있으므로, 각자 택시를 이용하는 비용과의 비교도 반드시 필요하다.
3. 어느 지점을 거쳐 이동할지 모르기 때문에, 각 지점까지의 거리를 계산하는 플로이드워셜 알고리즘을 활용할 수 있다.