[2021 카카오 블라인드 테스트] 합승 택시 요금

문제

0. 처음에 작성한 코드

from collections import deque

def dikstara(s, n, edge):
    visited = [False for _ in range(n+1)] # 해당 지점을 방문했는가 
    maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
    dist = [maxDist for _ in range(n+1)] # 해당 지점에 대한 최소 요금
    
    q = deque([(s, 0)])
    dist[s] = 0
    
    while q:
        v = q.popleft()
        x = v[0]
        
        # 재방문해도 더 빠를 수 있고, 재방문하면 안된다는 조건은 없으니 해당 코드는 삭제한다.
        # if visited[x] == True: 
        #     continue
        # visited[x] = True
        
        for k in edge[x]:
            if dist[k[0]] > dist[x] + k[1]: # 현재 저장된 k에 가는데 드는 비용 > x에 가는데 드는 비용 + x에서 k로 가는데 드는 비용   
                dist[k[0]] = dist[x] + k[1]
                q.append((k[0], dist[k[0]]))
    
    return dist
    
def solution(n, s, a, b, fares):
    answer = 0
    edge = [[] for _ in range(n+1)] # 간선별 요금 정보 저장 edge[출발지점] = [(도착지점, 요금)]  
    maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
    
    for fare in fares:
        edge[fare[0]].append((fare[1], fare[2]))
        edge[fare[1]].append((fare[0], fare[2]))
    
    startDist = dikstara(s, n, edge)
    answer = startDist[a] + startDist[b] # (S -> A) + (S -> B) 합승하지 않는 경우
    
    for i in range(1, n+1):
        if i != s and startDist[i] < maxDist:
            nDist = dikstara(i, n, edge) # 합승 -> A, B 최단 경로 요금 / 어떤 특정 지점을 시작 지점이라고 보고 다시 최단 경로를 찾는다.
            if answer > startDist[i] + nDist[a] + nDist[b]:
                answer = startDist[i] + nDist[a] + nDist[b] 
    
    return answer

solution(6, 4, 6, 2, [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]])

재방문 처리하는 코드를 삭제 했더니 어찌어찌 통과가 됐다. 그런데 다른 사람들의 풀이를 보니 다익스트라에 대해 완전히 잘못 알고 있었고, 플로이드 워셜이라는 알고리즘에 대해 알게 되었다.

두 알고리즘을 비교해보려 한다.

1. 다익스트라 알고리즘

• 시작 지점에서 모든 노드까지의 최단 경로를 구한다.
• 우선순위 큐(힙큐)를 이용하여 현재 방문하지 않는 노드(내가 잘못 알고 있었던 부분)들 중에서 이동하는데 드는 비용이 적은 노드들부터 방문하여 처리한다.
• 음의 비용이 존재하면 사용할 수 없다. (시작 지점에서 모든 노드까지의 최단 경로를 구해야하는데, 음의 비용이 존재한다면 벨만 포드 알고리즘을 사용한다.)

import heapq

def dijkstra(s, n, edge):
    visited = [False for _ in range(n+1)] # 해당 지점을 방문했는가 
    maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
    dist = [maxDist for _ in range(n+1)] # 해당 지점에 대한 최소 요금
    
    q = []
    heapq.heappush(q, (0, s))
    dist[s] = 0
    
    while q:
        v = heapq.heappop(q)
        x = v[1]
        
        if visited[x] == True: 
            continue
        visited[x] = True
        
        for k in edge[x]:
            if dist[k[0]] > dist[x] + k[1]: # 현재 저장된 k에 가는데 드는 비용 > x에 가는데 드는 비용 + x에서 k로 가는데 드는 비용   
                dist[k[0]] = dist[x] + k[1]
                heapq.heappush(q, (dist[k[0]], k[0]))
    
    return dist
    
def solution(n, s, a, b, fares):
    answer = 0
    edge = [[] for _ in range(n+1)] # 간선별 요금 정보 저장 edge[출발지점] = [(도착지점, 요금)]  
    maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
    
    for fare in fares:
        edge[fare[0]].append((fare[1], fare[2]))
        edge[fare[1]].append((fare[0], fare[2]))
    
    startDist = dijkstra(s, n, edge)
    answer = startDist[a] + startDist[b] # (S -> A) + (S -> B) 합승하지 않는 경우
    
    for i in range(1, n+1):
        if i != s and startDist[i] < maxDist:
            nDist = dijkstra(i, n, edge) # 합승 -> A, B 최단 경로 요금 / 어떤 특정 지점을 시작 지점이라고 보고 다시 최단 경로를 찾는다.
            if answer > startDist[i] + nDist[a] + nDist[b]:
                answer = startDist[i] + nDist[a] + nDist[b] 
    
    return answer

2. 플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다.
• 방문하지 않은 노드들 중에서 최소 비용을 갖는 노드를 찾을 필요가 없다. (다익스트라와의 차이점)
• 점화식: D(ab) = min( D(ab), D(ak)+ D(kb)) --> a에서 바로 b로 이동하는 거리와, a에서 k를 거쳐 b로 이동하는 거리중에 짧은 것을 택한다.
• 보통 노드의 개수가 500개 이하이다.
• 음의 비용이 존재해도 사용할 수 있다.

 def solution(n, s, a, b, fares):
    answer = 0
    maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
    dist = [[maxDist for _ in range(n+1)] for _ in range(n+1)] # dist[i][j] i에서 j까지 이동하는데 최소 비용
    
    for fare in fares:
        dist[fare[0]][fare[1]] = fare[2]
        dist[fare[1]][fare[0]] = fare[2]
    
    for i in range(1, n+1):
        dist[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 dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    answer = 40000000 # 원래 maxDist * 방문해야 하는 지점이 2개 
    for k in range(1, n+1):
        if answer > dist[s][k] + dist[k][a] + dist[k][b]:
            answer = dist[s][k] + dist[k][a] + dist[k][b]
        
    return answer