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

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

프로그래머스

알고리즘 분류

---

플로이드 워셜

 

풀이과정

---

출발지점 s에서 a와 b로 가는 경로에서 동승하는 구간을 포함한 최솟값을 구하는 문제이다.

시작점 s로부터 a와 b로의 최단거리를 구하는 방법은 `다익스트라` 또는 `플로이드 워셜` 알고리즘으로 쉽게 구할 수 있다. 그렇다면 동승 구간을 어떻게 처리할 지를 잘 생각해보면 된다.

시작점 s로부터 x지점까지 동승을 한다고 가정하면 요금 합은 `s -> x` + `x -> a` + `x -> b`가 된다.

노드는 최대 200개 이므로 x를 모든 노드에 대해서 순회해도 시간복잡도 내에 해결이 가능하다.

`s -> x`, `x -> a`, `x -> b`를 구해야 하므로 모든 노드에 대해 최단거리를 구할 수 있는 플로이드 워셜 알고리즘을 적용하고, x에 모든 노드 번호를 넣어가며 answer를 갱신하면 쉽게 답을 구할 수 있다.

 

소스코드

---

INF = float("inf")


def floyd(n, graph):
    dists = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dists[i][j] = graph[i][j]

    for k in range(1, n + 1):
        for s in range(1, n + 1):
            for e in range(1, n + 1):
                dists[s][e] = min(dists[s][e], dists[s][k] + dists[k][e])
    return dists
        

def solution(n, s, a, b, fares):
    answer = INF
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        graph[i][i] = 0
    for c, d, f in fares:
        graph[c][d] = f
        graph[d][c] = f
        
    dists = floyd(n, graph)
    
    # s -> x 까지 동승, x -> a, x -> b
    for x in range(1, n + 1):
        answer = min(answer, dists[s][x] + dists[x][a] + dists[x][b])
    return answer