[프로그래머스 LV 3] 합승 택시요금 (파이썬/python)

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

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

 

 

시작점 s

A의 도착지 a

B의 도착지 b

 

 

우선 각 노드에서 노드를 가는데 필요한 최단경로를 구한 후 

그 정보를 바탕으로 임의의 중간노드 t에 대해

 

금액(s+t) + 금액(t+a) + 금액(t+b) 

를 구해주면된다

 

플로이드와샬과 다익스트라 둘 다 써보았다

 

플로이드와샬

def solution(n, s, a, b, fares):
    INF = 10000000
    answer = INF
    graph = [[INF] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0

    for f in fares:
        node1, node2, fee = f
        graph[node1 - 1][node2 - 1] = fee
        graph[node2 - 1][node1 - 1] = fee

    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    for t in range(n):
        temp = graph[s - 1][t] + graph[t][a - 1] + graph[t][b - 1]
        answer = min(temp, answer)

    return answer

 

 

 

다익스트라

 

import heapq


def solution(n, s, a, b, fares):
    INF = 10000000
    answer = INF
    graph = [[] * (n + 1) for _ in range(n + 1)]

    for f in fares:
        node1, node2, fee = f
        # node1 - > node2 가는 요금이 fee
        graph[node1].append((node2, fee))
        # node2 - > node1 가는 요금이 fee
        graph[node2].append((node1, fee))

    def dijkstra(s):
        q = []
        # 최단거리 테이블을 무한으로 초기화
        distance = [INF] * (n + 1)
        # 거리(금액), 노드번호 순서
        heapq.heappush(q, (0, s))
        # 시작노드로 가는 최단거리는 0
        distance[s] = 0

        while q:
            dist, now = heapq.heappop(q)
            # 현재 노드가 이미 처리된 노드면 무시
            if distance[now] < dist:
                continue
                
            for g in graph[now]:
                cost = dist + g[1]
                if cost < distance[g[0]]:
                    distance[g[0]] = cost
                    heapq.heappush(q, (cost, g[0]))
        return distance

    distance_list = [[]] + [dijkstra(i) for i in range(1, n + 1)]

    for i in range(1, n + 1):
        answer = min(distance_list[s][i] + distance_list[i][a] + distance_list[i][b], answer)

    return answer