프로그래머스 등급3 - 합승 택시 요금

합승 택시 요금 문제 바로 가기

풀이 날짜: 2026-05-08

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq

def solution(n, s, a, b, fares):
    INF = int(1e9)
    
    graph = [[] for _ in range(n+1)]
    
    for x, y, cost in fares:
            graph[x].append((y,cost))
            graph[y].append((x,cost))
    
    def dijkstra(start):
        dist = [INF] * (n+1)
        
        q = []
        heapq.heappush(q,(0,start))
        dist[start] = 0
        
        while q:
            d,now = heapq.heappop(q)
            
            if dist[now] < d:
                continue
            
            for next_node, fare in graph[now]:
                cost = d + fare
                if cost < dist[next_node]:
                    dist[next_node] = cost
                    heapq.heappush(q,(cost,next_node))
        
        return dist

    dist_s = dijkstra(s)
    dist_a = dijkstra(a)
    dist_b = dijkstra(b)
    
    answer = INF
    
    for i in range(1,n+1):
        answer = min(answer, dist_s[i] + dist_a[i] + dist_b[i])
    
    return answer

문제 핵심

처음 문제를 봤을 때는 “최단 거리” 문제라는 점에서 다익스트라 알고리즘을 떠올렸다. 시작 지점 s에서 A의 목적지 a, B의 목적지 b까지 이동해야 하고, 일부 구간은 함께 이동할 수 있기 때문에 단순히 s → a, s → b 최단거리만 구해서는 해결되지 않았다. 핵심은 “어디까지 함께 이동한 뒤 갈라지는 것이 가장 이득인가”를 찾는 것이었다.

접근 방법 (아이디어)

합승 택시는 중간 지점 k까지는 함께 이동하고, 이후 각자 목적지로 이동하는 구조라고 생각할 수 있다. 즉, 전체 비용은 다음처럼 나뉜다.

s → i : 함께 이동
i → a : A 혼자 이동
i → b : B 혼자 이동

따라서 모든 정점 i를 “합승을 끝내고 갈라지는 지점”이라고 가정해보고, 그 중 가장 비용이 작은 경우를 찾는 방식으로 접근했다.

그래프 구성

입력으로 주어지는 fares는 [출발지, 도착지, 비용] 형태였다. 또한 이 문제는 양방향 그래프이므로 모두 이동 가능하다. 그래서 인접 리스트 형태의 그래프를 만들고 양쪽 모두 저장했다.

graph[x].append((y, cost))
graph[y].append((x, cost))

다익스트라를 선택한 이유

처음에는 BFS도 떠올렸지만, 이 문제는 간선마다 비용이 서로 다르다. BFS는 모든 간선의 가중치가 동일할 때만 최단거리를 보장한다. 반면 이 문제에서는 요금(cost)이 다양하므로, 현재까지의 누적 비용이 가장 작은 경로부터 탐색하는 다익스트라 알고리즘이 적합했다.

우선순위 큐(heapq)를 사용해 가장 비용이 적은 경로를 먼저 꺼내도록 구현했다.

heapq.heappush(q, (비용, 노드))

다익스트라 함수 구현

다익스트라 함수에서는 먼저 모든 노드까지의 거리를 무한대로 초기화했다. 그리고 시작 노드의 거리를 0으로 설정했다. 이후 현재 비용이 가장 작은 노드를 꺼내고, 연결된 노드들을 확인하면서 더 짧은 경로가 발견되면 거리 배열을 갱신했다.

cost = d + fare

처음 헷갈렸던 부분

장 헷갈렸던 부분은 다음 코드였다.

dist_s = dijkstra(s)
dist_a = dijkstra(a)
dist_b = dijkstra(b)

처음에는 dijkstra(s)를 하면 s 하나의 값만 나오는 줄 알았다. 하지만 실제로 다익스트라는 “특정 시작점에서 모든 노드까지의 거리 배열”을 반환한다. 즉, dist_s[i]는 s에서 i까지의 최단거리라는 의미이다.

왜 모든 i를 확인하는가

합승 택시는 특정 지점까지 함께 이동하다가 갈라지는 구조이다. 그런데 어느 지점에서 갈라지는 것이 가장 저렴한지는 알 수 없다. 따라서 for i in range(1, n+1): 를 통해 모든 정점을 “학습 종료 지점”이라고 가정해보는 것이다. 그리고 dist_s[i] + dist_a[i] + dist_b[i]를 계산한다.

최종 비용 계산

모든 정점 i를 확인하면서 가장 작은 비용을 정답으로 선택했다.

answer = min(answer, dist_s[i] + dist_a[i] + dist_b[i])

즉 “어디까지 같이 이동하는 것이 가장 효율적인가”를 전부 시도한 뒤 최소값을 선택하는 방식이었다.

구현 과정에서 실수했던 부분

처음 구현할 때는 dist 배열을 함수 밖에 선언했는데, 이렇게 하면 다익스트라를 여러 번 실행할 때 이전 결과가 남아 문제가 발생했다. 따라서 dist는 반드시 dijkstra() 내부에서 새로 생성해야 했다.

배운 점

이번 문제를 통해 다익스트라가 단순히 한 목적지까지의 최단거리만 구하는 알고리즘이 아니라, “한 시작점에서 모든 노드까지의 최단거리 배열”을 반환한다는 점을 명확하게 이해할 수 있었다. 또한 문제를 “합승 후 분기” 구조로 단순화해서 생각하니 풀이 흐름이 훨씬 쉽게 보였고, 여러 시작점에서의 최단거리 결과를 조합해 새로운 문제를 해결할 수 있다는 점도 배울 수 있었다.

Vienna sausage