최단 경로 (2) 썸네일형 리스트형 합승 택시 요금 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다. 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 .. 백준 10217 KCM Travel - 파이썬 문제. 풀이. 우선 처음에는 다익스트라를 이용하여 풀이를 했다. 처음에는 답이 틀렸다. 그 이유는 비용으로 비교했을때 거리와, 거리로 비교했을때 최소거리 2가지 경우를 모두 생각해야 했었다. 그래서 두 가지 경우를 나눠서 제출을 했는데 이번에는 메모리 초과로 틀렸다. 우선 기존 소스코드를 첨부하겠다. 기존 소스코드. import sys import heapq def dijkstra(start): global dp visited = [False for i in range(N+1)] dp_time[start] = [0, 0] dp_cost[start] = [0, 0] heap = [] heapq.heappush(heap, [0, start, 0]) #[비용, 위치, 시간] while heap: now_cos.. 이전 1 다음
