[python] 최단 경로 문제

최단 경로 문제

최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제다.

다익스트라 알고리즘

항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy) 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다. 다익스트라 알고리즘은 노드 주변을 탐색할때 BFS를 이용하는 대표적인 알고리즘이다.

쉽게 설명하자면 DFS 는 미로를 한 사람이 찾아 헤매는 과정이고 BFS는 여러 명의 사람이 각기 서로 다른 갈림길로 흩어져서 길을 찾는 것이다. 이때 다익스트라 알고리즘은 먼저 도착한 사람의 실뭉치를 사용해 탈출구를 찾아 나가는 것이다.

문제 1. 네트워크 딜레이 타임

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

ex)

• 입력 : times = [ [2,1,1],[2,3,1],[3,4,1]], N = 4 , K = 2
• 출력 : 2

다익스트라 알고리즘 구현을 이용한 풀이

import collections
import heapq
def networkDelayTime(times,N,K):
    graph = collections.defaultdict(list)
    # 그래프 인접 리스트 구성
    for u , v , w in times:
        graph[u].append((v,w))
        
    # 큐 변수 : [(소요 시간, 정점)]
    Q = [(0,K)]
    dist = collections.defaultdict(int)
    
    # 우선순위 큐 최솟값 기준으로 정점까지 최단 경로 삽입
    while Q:
        time, node = heapq.heappop(Q)
        if node not in dist:
            dist[node] = time
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(Q,(alt,v))
    
    # 모든 노드의 최단 경로 존재 여부 판별
    if len(dist) == N:
        return max(dist.values())
    return -1

• graph 는 현재 노드의 소요시간과 도착가능한 노드를 입력한 딕셔너리이다. Q는 처음 입력받은 정점인 K에서 시작하고 소요시간이 기본으로 0이기 때문에 (0,K)를 넣고 시작한다.

• heap을 통해 시간이 제일 적게 걸리는 도착지를 탐색하고 그때의 노드가 dist 딕셔너리에 있다면 그 값은 이미 최단 경로이고, 그 값은 버리게 된다. 만약 dist에 존재하지 않는다면 바로 dist값으로 time과 node의 순서가 바뀌면서 입력된다. (dist는 최소값부터 세팅되기 때문에 처음 입력값이 최솟값이다.)

• dist 딕셔너리의 키 개수가 N과 동일한지 체크하는 이유는, 전체 노드 개수만큼 dist에 있다면 모든 노드의 최단 경로를 구했다는 뜻이고 모두 시작점에서 도달 가능하다는 의미이기 때문이다. 노드가 하나라도 없으면 방문하지 않은 노드가 있는 것이므로 -1 을 리턴한다.

문제 2. K 경유지 내 가장 저렴한 항공권

시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다.

ex)

• 입력 : n = 3 , edges = [[0,1,100],[1,2,100],[0,2,500]] , src = 0 , dst = 2, K = 0
• 출력 : 500

다익스트라 알고리즘 응용

import collections
import heapq
def findCheapestPrice(n,flights,src,dst,K):
    graph = collections.defaultdict(list)
    #그래프 인접 리스트 구성
    for u,v,w in flights:
        graph[u].append((v,w))
        
    # 큐 변수: [(가격, 정점, 남은 가능 경유지 수)]
    Q = [(0,src,K)]
    
    # 우선순위 큐 최솟값 기준으로 도착점까지 최소 비용 판별
    while Q:
        price,node,k = heapq.heappop(Q)
        if node == dst:
            return price
        
        if k>= 0 :
            for v, w in graph[node]:
                alt = price + w
                heapq.heappush(Q,(alt,v,k-1))
                
    return -1

• 앞서 사용했던 알고리즘과 비슷한 구조로 진행이 된다.

• 방문할 수 있는 경유지 수 k가 while문이 한번 진행될 때 마다 1씩 감소하고 k<0 이 되면 heappush 를 그만한다. ( 즉, 탐색을 중단한다. ) 그리고 while문에서 중간에 리턴이 일어나지 않을 시 K개의 경유지 내에 방문이 불가한 것이므로 -1을 리턴한다.

• node와 dst가 같을 때, 가격을 리턴하는데 heap에 의해 가격의 최소값이 출력된다.

• 밑에 예시를 본다면, 경유지 수에 따른 차이를 알 수 있다.

findCheapestPrice(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)

500

findCheapestPrice(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)

200