프로그래머스 72413 합승 택시 요금 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2411295

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

---

문제

그림이 너무 크고 많아서 링크로 이동해서 문제를 확인하시길 추천드립니다.

---

아이디어

• 출발지에서 모든 도착지에 대해 다익스트라 알고리즘으로 최소 비용 탐색
• 반복문을 순회하며 모든 장소에서 a, b의 목적지까지 최소 비용 탐색하고 최소값 저장

---

전체 풀이 코드

import heapq

def solution(n, s, a, b, fares):
    answer = int(1e9)
    road = [[] for _ in range(n + 1)]
    
    # 최소비용 탐색
    def djikstra(start):
        visited = [int(1e9)] * (n + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])
        
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in road[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after])
                            
        return visited
    
    
    # 입력 처리
    for i in range(len(fares)):
        start, end, cost = fares[i]
        road[start].append([cost, end])
        road[end].append([cost, start])
    
    # 출발지에서 모든 도착지까지 최소 비용 탐색
    together = djikstra(s)
    
    # 각 도착지에서 A,B 최소 비용 탐색
    for i in range(1, n + 1):
        route = djikstra(i)
        answer = min(together[i] + route[a] + route[b], answer)
    
    return answer

---

상세 풀이 코드

import heapq

def solution(n, s, a, b, fares):
    answer = int(1e9)
    load = [[] for _ in range(n + 1)]

• answer : 최소 비용을 저장할 변수. 최초에는 큰 수로 설정
• load : 각 번호의 장소와 연결된 장소, 비용을 저장할 2차원 배열

 

 # 최소비용 탐색
    def djikstra(start):
        visited = [int(1e9)] * (n + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])
        
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in load[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after])
                            
        return visited

• 다익스트라 알고리즘 코드 구현
• visited : start에서 각 번호까지 드는 비용 기록, 최초에는 큰 값으로 설정
• 힙큐에 [비용, 장소] 추가
• 힙큐가 있는 동안, 비용과 현재 장소 pop
• 만약, 지금까지의 비용이 현재 경로에 저장된 비용보다 크다면, 최소비용이 될 수 없으므로 고려하지 않음
• add, after : 다음 경로까지의 비용, 다음 도착지 정보
• 만약 다음경로까지 기록된 최소비용 보다 현재 이동할 경로가 싸다면 visited[after] 재할당, 힙큐에 추가
• 최종적으로 모든 도착지에 대한 최소 비용을 저장한 visited 반환

 

    # 입력 처리
    for i in range(len(fares)):
        start, end, cost = fares[i]
        load[start].append([cost, end])
        load[end].append([cost, start])

• 주어지는 경로 입력 처리 과정
• fares[i]에 담긴 출발지, 도착지, 비용 정보를 양방향 저장

 

    # 출발지에서 모든 도착지까지 최소 비용 탐색
    together = djikstra(s)
    
    # 각 도착지에서 A,B 최소 비용 탐색
    for i in range(1, n + 1):
        route = djikstra(i)
        answer = min(together[i] + route[a] + route[b], answer)
    
    return answer

• together : 합승 택시 요금 계산. 출발지에서부터 모든 경로로의 다익스트라 탐색 진행
• for 반복문 : 출발지에서 이동한 모든 장소에서 새로 출발하여 다익스트라 탐색 진행
• route : 합승 후 출발지 i에서 모든 장소로의 최소 비용을 저장
• answer : 기록된 answer와 합승구간 비용, A, B의 합승 후 개인 이동 비용 중 작은 값 저장

---

느낀점

• 처음에는 A, B의 다익스트라 배열을 구해두고, 한 칸씩 따라가는 방식으로 코드를 짰는데, 반례가 생각나서 바꿨다.
• 모든 경로에 대해서 다익스트라 함수를 실행하고, 다시 모든 장소에서 출발하며 다익스트라 함수를 진행하면 너무 비효율적일거라고 생각했는데, 통과가 되어서 어디 고칠 데 없나 좀 들여다보고 수정했다.
• 우선, A, B의 비용을 한 번에 구할 수 있으니까 기존에는 route 선언 없이 djikstra를 구하던 방식에서 한 번 함수 실행 결과를 저장하고 a, b 최소 비용을 가져오는 방식으로 수정했다. 시간이 절반 정도로 줄어든 것들도 있어서 조금 뿌듯한 상태
• 자바로도 풀어보고 싶은데 아직 너무 어려운 것 같다ㅠ

---

성능 비교

• 왼쪽 코드가 마지막 for 반복문에서 djikstra 두 번 부를 때, 오른쪽 코드가 한 번 부를 때 시간이다.