PS
[Programmers] Python 합승 택시 요금 (72413)
1223v
2025. 2. 22. 00:44
https://school.programmers.co.kr/learn/courses/30/lessons/72413
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
다익스트라 응용 문제이다.
1. a, b 각각 가는 비용을 다익스트라로 구한다.
2. a, b 각각 구한 비용을 중심으로 비교할 대상을 반복을 돌며,
(s -> i 의 동행 거리) + (i -> a 거리) + (i -> b 거리) 가 최소가 되는 것을 찾으면 된다.
import heapq
def solution(n, s, a, b, fares):
answer = 0
graph=[[] for _ in range(n+1)]
for start, end, cost in fares:
graph[start].append((end,cost))
graph[end].append((start, cost))
def dijkstra(start):
hq = []
distance = [float('inf')] * (n+1)
distance[start] = 0
heapq.heappush(hq,(0,start))
while hq:
dist, now_node = heapq.heappop(hq)
for next_node, cost in graph[now_node]:
if distance[next_node] > dist+cost:
distance[next_node] = dist + cost
heapq.heappush(hq,(dist+cost, next_node))
return distance
origin_distance = dijkstra(s)
result = origin_distance[a] + origin_distance[b]
for i in range(n+1):
if i == s:
continue
else:
ab_distance=dijkstra(i)
result = min(result, origin_distance[i] + ab_distance[a] + ab_distance[b])
return result
print(solution(6,4,6,2, [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]))
회고.
다익스트라를 부분적으로 잘라서 하는 문제를 풀어봤으나 이런식으로 나누는 것을 새로운 느낌이였다. 도움이 많이 된 문제였다.
728x90