사용자 도구

사이트 도구


ps:problems:programmers:72413

합승 택시 요금

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호72413
문제명합승 택시 요금
레벨Level 3
분류

그래프

시간복잡도O(n^2)
인풋사이즈n<=200
사용한 언어Python
해결날짜2021/01/26

풀이

  • 합승해서 x까지 같이 간 뒤에, x에서 부터는 따로 택시를 타고 a와 b로 간다면 총 요금은 cost[s][x] + cost[x][a] + cost[x][b].
  • 모든 x에 대한 cost[s][x], cost[x][a], cost[x][b]의 값을 계산해놓는다면, min_x(cost[s][x] + cost[x][a] + cost[x][b]) 는 O(n)에 계산가능
    • 그냥 전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP) 알고리즘을 써서 cost[x][y]를 다 구해놓으면 O(n^3)으로 비효율적이지만, 통과는 된다.
    • 이 문제에서는 cost[…][a] = cost[a][…], 이므로 cost[a][…], cost[b][…], cost[s][…]를 각각 다익스트라 알고리즘으로 구하는 편이 좀더 효율적이다. 문제에서 E≤O(V^2)으로 주어졌으므로, 시간 복잡도를 O(ElogV)대신 O(V^2)으로 표현하는것이 더 나을듯. 실제 구현은 O(ElogV)의 구현으로 처리했다.
  • cost를 모두 구했으면, min을 계산하는 것은 O(n)이다.

코드

"""Solution code for "Programmers 72413. 합승 택시 요금".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72413
- Solution link: http://www.teferi.net/ps/problems/programmers/72413
"""

from teflib import tgraph


def solution(n, s, a, b, fares):
    wgraph = [{} for _ in range(n)]
    for c, d, f in fares:
        wgraph[c - 1][d - 1] = wgraph[d - 1][c - 1] = f
    dists_s = tgraph.dijkstra(wgraph, s - 1)
    dists_a = tgraph.dijkstra(wgraph, a - 1)
    dists_b = tgraph.dijkstra(wgraph, b - 1)
    return min(dists_s[x] + dists_a[x] + dists_b[x] for x in range(n))

토론

댓글을 입력하세요:
T​ L A R D
 
ps/problems/programmers/72413.txt · 마지막으로 수정됨: 2024/03/14 08:35 저자 teferi