[프로그래머스] Level3, 합승 택시 요금 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/72413?language=python3 

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

 

코드

import heapq
import sys

def solution(n, s, a, b, fares):
    answer = sys.maxsize
    
    def dijkstra(start):
        INF = sys.maxsize
        distance = [INF for _ in range(n+1)]
        distance[start] = 0
        heap = []
        heapq.heappush(heap, (0, start))

        while heap:
            wei, now = heapq.heappop(heap)
            if distance[now] < wei:
                continue
            for w, next_node in graph[now]:
                next_wei = w + wei
                if next_wei < distance[next_node]:
                    distance[next_node] = next_wei
                    heapq.heappush(heap, (next_wei, next_node))
        return distance
    
    graph = [[] for _ in range(n+1)]
    for i in range(len(fares)):
        graph[fares[i][0]].append((fares[i][2], fares[i][1]))
        graph[fares[i][1]].append((fares[i][2], fares[i][0]))
    
    
    for i in range(1, n+1): 
        distance_1 = dijkstra(s)
        distance_2 = dijkstra(i)
        answer = min(answer, distance_1[i] + distance_2[a] + distance_2[b])
    return answer

fares를 우선순위 큐에 넣기 편하게 graph로 새로 리스트를 만들어서 저장해주고 dijkstra를 돌린다.

 

맨처음 출발점 s일때 다익스트라를 돌려 s부터 모든 정점에 최단거리를 구하고

 

a,b 목적지 까지에 최소비용을 찾기위해서 비용이 가장 적게드는 환승 지점을 찾기 위해 for문을 돌려 1부터 n 정점까지 모두 다익스트라를 돌려본다.

 

출발지점 s에서 환승지점 i 까지 비용 + i 환승지점에서 a 목적지 까지 비용 + i 환승지점에서 b 목적지 까지 비용이

가장 작은 값을 구한다.

 

플로이드 풀이

import sys

def floyd(distance, n):
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
    return distance
    
def solution(n, s, a, b, fares):
    INF = sys.maxsize
    answer = INF
    distance = [[INF for _ in range(n+1)] for _ in range(n+1)]
    
    for edge in fares:
        distance[edge[0]][edge[1]] = edge[2]
        distance[edge[1]][edge[0]] = edge[2]
    
    for i in range(1, n+1):
        distance[i][i] = 0
    
    distance = floyd(distance, n)
    
    for k in range(1, n+1): # 합승지점 k 까지 간후 a,b 목적지 갈때 제일 작은값
        answer = min(answer, distance[s][k] + distance[k][a] + distance[k][b])
    
    return answer