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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 합승 택시 요금

새로 알게된 것들

그래프 또는 맵이 나오고 최소비용에 대한 말이 나오면 플로이드 와샬, 다익스트라 알고리즘을 떠올려야 겠다.

플로이드 와샬 알고리즘
모든 노드에서 모든 노드까지의 최소거리를 구하는 알고리즘. 노드와 노드 사이의 간선이 음수일 경우에도 성립한다. 시간복잡도는 O(N^3)

다익스트라 알고리즘
한 노드에서 모든 노드까지의 최소거리를 구하는 알고리즘. 노드와 노드 사이의 간선이 음수일 경우에는 성립하지 않는다. 시간복잡도는 O(NlogN)

풀이

처음에는 플로이드 와샬 알고리즘을 몰라 다익스트라 알고리즘을 N번 반복하면 되지 않을까란 생각으로 풀었다.
1. 우선순위큐를 사용하기 때문에 import heapq를 해준다.
2. 최대 택시요금은 200 X 100,000보다 클 수 없어 200,000,001을 최대값으로 상수를 초기화한다.
3. 주어진 간선들을 map을 이용해서 인접 리스트로 만들어 저장한다. (인접 행렬로 구현해도 됨)
4. 각 노드마다 다익스트라 알고리즘으로 사용하여 모든 노드에서 모든 노드까지의 최소 비용을 구한다.
5. 시작점과 도착점 2개가 모두 정해져 있기 때문에 중간 노드만 어떤 노드를 사용할 때 최소가 되는지 반복문을 돌려 구한다.

코드 1 (다익스트라)

import heapq

def solution(n, s, a, b, fares):
    MAX_PRICE = 20000001
    
    graph = {i + 1 : {} for i in range(n)}
    
    for v1, v2, value in fares:
        graph[v1][v2] = value
        graph[v2][v1] = value
        
    minPriceGraph = {i + 1 : {j + 1 : MAX_PRICE for j in range(n)} for i in range(n)}
    def dijkstra(start):
        pq = [[0, start], ]
        while pq:
            price, curr = heapq.heappop(pq)
            if minPriceGraph[start][curr] < price:
                continue
            minPriceGraph[start][curr] = price 				# 여기서 초기화할 때는 초기값을 설정하지 않았을 때
            for next in graph[curr]:
                newPrice = price + graph[curr][next]
                if newPrice < minPriceGraph[start][next]:
                    # minPriceGraph[start][next] = newPrice # 여기서 초기화할 때는 초기값을 설정했을 때
                    heapq.heappush(pq, [newPrice, next])
    
    for i in range(1, n + 1):
        dijkstra(i)
            
    minPrice = MAX_PRICE
    for i in range(1, n + 1):
        minPrice = min(minPrice, minPriceGraph[s][i] + minPriceGraph[i][a] + minPriceGraph[i][b])
    
    return minPrice

코드 2 (플로이드 와샬)

def solution(n, s, a, b, fares):
    
    MAX_PRICE = 20000001
    graph = [[MAX_PRICE for i in range(n + 1)] for i in range(n + 1)]
    
    for x, y, price in fares:
        graph[x][y] = price
        graph[y][x] = price
    
    for i in range(1, n + 1):
        graph[i][i] = 0
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    
    answer = MAX_PRICE
    for i in range(1, n + 1):
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b])
    
    return answer

느낀점

다익스트라 알고리즘을 N번 한 시간이 플로이드 와샬을 한 시간보다 더 빠를 줄 알았으나 플로이드 와샬을 적용한 코드가 더 빨랐다. 정확하게는 모르겠지만 다익스트라 알고리즘을 최적화 시키지 않아서 그런 것 같다.
플로이드 와샬, 다익스트라, 너비우선탐색 등 거리를 탐색하는 알고리즘이 많아 하루날 잡고 차이점과 정확히 어떻게 동작하는지 공부해야 겠다.