[프로그래머스] 합승 택시 요금 / KAKAO BLIND RECRUITMENT / 파이썬

문제

코딩테스트 연습 - 합승 택시 요금

풀이

1. 택시가 이동할 수 있는 경로 마다 예상 택시 요금이 있는데 a와 b가 s에서 출발하여 가장 적은 요금으로 둘 다 귀가를 하는 것이 목적입니다.

2. 지점 별로 최소 예상 요금을 요구하기 때문에 다익스트라 알고리즘을 사용하면 쉽게 풀릴 것입니다.

3. 문제에서 원하는 목적을 약간 다르게 생각해 본다면, 굳이 s에서 출발해야 한다는 생각을 버리고, 모든 지점에서 출발하여 s, a, b에 도착할 수 있는 최소 요금을 구하고 그중 최솟값으로 택하면 됩니다.

❗️예를 들어 지점이 1, 2, 3, 4가 있고 s = 1, a = 2, b = 3이라면
1. 1에서 s, a, b 의 최소 요금의 합 (이때 s 지점과 1은 동일하기 때문에 0임)
2. 2에서 s, a, b 의 최소 요금의 합 (이때 a 지점과 2은 동일하기 때문에 0임)
3. 3에서 s, a, b 의 최소 요금의 합 (이때 b 지점과 3은 동일하기 때문에 0임)
4. 4에서 s, a, b 의 최소 요금의 합
중 가장 적은 요금의 합이 정답입니다.
또한 고립되어 있는 지점은 따로 예외 처리를 해줍니다.

다익스트라 알고리즘을 아직 배우지 않았다면 여기를 참고해 주세요. 알고리즘에 대해 설명을 잘 해주는 블로그입니다.

 

코드

from heapq import heappush, heappop
MAX_SIZE = 10000000


def solution(n, s, a, b, fares):
    s, a, b = s-1, a-1, b-1
    adj = [[] for _ in range(n)]
    h = []
    for u, v, w in fares:
        u, v = u-1, v-1
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    answer = []
    
    # 모든 정점을 탐색
    for node in range(n):
        dist = [MAX_SIZE for _ in range(n)]
        dist[node] = 0
        heappush(h, (0, node))
        while h:
            _, curr = heappop(h)
            for nxt, cost in adj[curr]:
                if dist[curr] + cost < dist[nxt]:
                    dist[nxt] = dist[curr] + cost
                    heappush(h, (cost, nxt))
            if dist[a] + dist[b] + dist[s]:
                answer.append(dist[a] + dist[b] + dist[s])

    return min(answer)