[Python] 프로그래머스 - 합승 택시 요금

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

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

# 2021 카카오 블라인드 코딩테스트 문제이다.

# 그냥 문제를 보면 '그래프' 문제인 것을 알 수 있다.

# N이 200이하이므로 O(N^3)인 플로이드-와샬 알고리즘이랑 O(E logV)인 다익스트라를 생각해볼 수 있다.

 

1. 플로이드-와샬 

    * 그래프탐색의 완전탐색이라고 할 수 있는 플로이드-와샬이다.

     

    1-1. fares에 있는 지점들 사이의 택시요금 cost를 갱신해주고 floyd_warshall함수를 실행한다.

 

    1-2. floyd_warshall함수: k를 1부터 n번 지점까지 돌면서 i에서 k를 거쳐 j까지 가는 cost를 갱신해준다.

 

    1-3. i를 A와 B가 같이가는 지점이라고 가정하고, 1부터 n까지 반복문을 돌며

          s에서 i까지의 비용 + i에서 a까지의 비용 + i에서 b까지의 비용을 구해 ans와 비교해 작은 값을

          ans에 넣어준다.  모든 지점을 다 확인한 뒤 ans를 return해준다.

 

def solution(n, s, a, b, fares):
    ans = 200000001
    cost = [[20000001] * (n+1) for _ in range(n+1)]
    def floyd_warshall():
        for k in range(1, n+1):
            for i in range(1, n+1):
                for j in range(1, n+1):
                    if i == j:
                        cost[i][j] = 0
                    else:
                        cost[i][j] = min(cost[i][k] + cost[k][j], cost[i][j])
        
    for i, j, c in fares:
        cost[i][j] = c
        cost[j][i] = c
    floyd_warshall()
        
    for i in range(1, n+1):
        ans = min(cost[s][i] + cost[i][a] + cost[i][b], ans)
    return ans

 

========================================================================

 

2. 다익스트라

   # 대부분의 케이스에서 플로이드-와샬보다 빠른속도를 보여주었지만

      케이스 하나에서 3700ms가 나왔다. 간선의 개수가 많아지면 더 느려지는 것 같다.

    

    # 플로이드와샬 (270ms ~ 2300ms), 다익스트라 (15ms ~ 1600ms, 3700ms)

 

import heapq
def solution(n, s, a, b, fares):

    def dijkstra(start):
        res = [float('INF') for _ in range(n+1)]
        res[start] = 0
        q = []
        heapq.heappush(q, (res[start], start))
        while q:
            result_x, x = heapq.heappop(q)
            for fu, fw in graph[x]:
                if res[fu] > result_x + fw:
                    res[fu] = result_x + fw
                    heapq.heappush(q, ([res[fu], fu]))
        return res

    ans = 200000001
    graph = [[] for _ in range(n+1)]
    for i, j, c in fares:
        graph[i].append((j, c))
        graph[j].append((i, c))
    
    dist = [[]]
    for i in range(1, n+1):
        dist.append(dijkstra(i))

    for i in range(1, n+1):
        ans = min(ans, dist[s][i] + dist[i][a] + dist[i][b])
    return ans

 

(프로그래머스 level: 3)