프로그래머스 - 합승 택시 요금(2021 KAKAO BLIND RECRUITMENT)

프로그래머스 - 합승 택시 요금(2021 KAKAO BLIND RECRUITMENT)

간단했지만 제출하고 정확성 마지막에서 실패가 나와서 당황했다.. 어디가 문제인지 찾지 못하다가 초기 거리의 값 설정에 문제가 있는 것 같아서 100001에서 100000001로 MAX값을 올리니 통과했다... 요금F는 1 이상 100,000 이하인 자연수라는 말만 보고 100001로 설정해서 고생했다.. 만약 N명의 요금이 모두 100,000이라면 100001이 훌쩍넘어가기에 다시 설정해 주어야한다. 풀이는 힙큐를 이용하는 다익스트라를 사용하였고 우선 시작 지점에서 모든 경로의 최단거리를 구해주었다. 이 후 시작점 까지 동승하고 내려서 각자 집까지의 거리를 answer값으로 설정해주었다.(시작점에서 동승하지 않고 각자 간 경우가 더 빠를 수도 있으므로)이 후 시작점을 제외하고 모든 지점을 시작점으로 a와의 최단거리, b와의 최단거리를 구해서 더해준 후 설정한 최솟값과 비교하여 최저 택시요금을 정답을 도출 할 수 있다. 주의 할 점은 시작점을 제외하고 모든 위치에서 최단거리를 구할 때 a지점에서 시작 할 수도 b지점에서 시작 할 수 도 있다. 이럴 경우 해당 시작점의 값을 0으로 초기화 시켜야한다.
코드를 보면 이해하기 수월하다.

코드

import heapq
def dj(start_node,visited,graph,n,a,b):
    visited = [100000001 ] * (n+1)
    route = []
    heapq.heappush(route, (0,start_node))
    while route:
        cost, node = heapq.heappop(route)
        for e_node, e_cost in graph[node]:
            next_cost = e_cost + cost
            if next_cost < visited[e_node]:
                visited[e_node] = next_cost
                heapq.heappush(route,(next_cost,e_node))

    return visited[a], visited[b] , visited

def solution(n, s, a, b, fares):
    # (start_node,visited,graph,n)
    graph = []
    for _ in range(n+1):
        graph.append([])
    for c,d,f in fares:
        graph[c].append((d,f))
        graph[d].append((c,f))
    visited = [1000000] * (n+1)
    ca,cb, tmp_visited = dj(s,visited,graph,n,a,b)
    answer = ca + cb
    for i in range(1,n+1):
        dist = tmp_visited[i]
        if s == i:
            continue
        c_a, c_b, tmp = dj(i,visited,graph,n,a,b)
        #만약 a에서 시작해서 탐색했다면
        if i == a:
            # 거리를 0으로 초기화
            c_a = 0
        if i == b:
            # 해당 거리를 0으로 초기화
            c_b = 0
        dist = dist + c_a + c_b
        answer = min(answer, dist)
    return answer