[프로그래머스Lv.3] 합승택시요금(파이썬)

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

프로그래머스

문제접근

 

1. 그래프를 사용하는 문제다

2. 최저요금이니깐 다익스트라를 쓰면 되겠구나

 

어려웠던 지점

합승??? 합승을 끝내는 지점or합승을 안하는 경우를 어떻게??

A,B각각을 S까지 갈 때의 최소비용을 구할까?

그럼 합승할 때 겹치는 걸 빼야하는데 이게 안되는데....

시작점-합승끝내는 지점을 각각 구하고

그 지점에서 a,b거리를 구한다?

그럼 시작점-합승사이 bfs해주고

합승끝부터 a,b거리 bfs해주니깐

시간초과가 뜰 수 밖에 없는 구조인데??

 

해결책

플로이드 워셜 알고리즘을 사용합니다.

이 알고리즘을 활용해서 

각 지점을 기준으로 다른 지점까지 얼마의 돈을 지불하면 갈수있는지 구합니다.

처음에는 시작점 기준, 각 지점을 얼마면 갈 수 있는지 구하고

1~n까지 각각을 합승이 끝나는 지점이라고 생각하고

각 지점의 지점 간 비용을 구합니다.

그 후, 시작점->합승+합승->a+합승+b의 비용이 최소가 되는 값을 리턴합니다.

 

풀이코드

from heapq import heappop, heappush


def masha(n, graph, start):
    distance = [1e9] * (n + 1)
    q = []
    heappush(q, [0, start])
    distance[start] = 0

    while q:

        nct, now = heappop(q)

        for go, cost in graph[now]:
            nexCost = nct + cost
            if nexCost < distance[go]:
                distance[go] = nexCost
                heappush(q, [nexCost, go])

    return distance


def solution(n, s, a, b, fares):
    answer = 1e9
    graph = [[] for _ in range(n + 1)]

    for x, y, cost in fares:
        graph[x].append([y, cost])
        graph[y].append([x, cost])
    # 시작점에서 각 점까지의 거리를 마샬로 구함
    d1 = masha(n, graph, s)

    # 환승이 끝나는 지점을 구하고 그 거리에서 a,b,시작점까지의 거리를 구해보자
    for i in range(1, n + 1):
        d2 = masha(n, graph, i)
        if answer > d1[i] + d2[a] + d2[b]:
            answer = d1[i] + d2[a] + d2[b]
    return answer