[프로그래머스] 합승 택시 요금 - Python

🤔 문제

---

https://programmers.co.kr/learn/courses/30/lessons/72413?language=python3 

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

😀 풀이

---

이 문제에서 합승 택시 요금의 최소 값을 구하기 위해서는 아래의 값이 필요합니다.

• S -> X 까지 가는 데 드는 최소값
• X -> A 까지 가는 데 드는 최소값 
• X -> B 까지 가는 데 드는 최소값

위의 세 가지 값을 더한 값, 즉 S -> X 까지는 합승하고 X 에서부터 A, B가 따로가는 경우의 총 요금을 모든 X에 대해 구해보고 그 중 최소값을 구하면 정답을 구할 수 있습니다.

 

따라서 임의의 노드 a, b에 대하여 a -> b 로 가는데 드는 최소값을 알고 있어야하고 이를 위해 플로이드 워셜 알고리즘을 적용합니다. 플로이드 워셜 알고리즘에 대한 내용은 많이 나와있으므로 따로 설명하지 않고 바로 풀이 코드를 첨부하겠습니다.

 

💻 풀이 코드는 아래와 같습니다.

def solution(n, s, a, b, fares):
    INF = int(1e9)
    answer = INF
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    for start, dest, fare in fares:
        graph[start][dest] = fare
        graph[dest][start] = fare
    
    for i in range(1, n + 1):
        graph[i][i] = 0

    # 플로이드 워셜 알고리즘
    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 i in range(1, n + 1):
        cost = graph[s][i] + graph[i][a] + graph[i][b]
        answer = min(answer, cost)    

    return answer