최단 경로 문제

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

최단 경로는 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 쉽게 말해 내비게이션에서 목적지로 이동할 때, 경로 탐색을 하면 나오는 최적의 경로 문제가 바로 최소 비용이 되는 최단 경로 문제이다. 이때 정점(Vertex)는 교차로에 해당하고, 간선(Edge)는 길에 해당한다. 가중치(Weight)는 거리나 시간과 같은 이동 비용에 해당한다.

이러한 문제를 해결하기 위한 단 하나의 가장 좋은 풀이 알고리즘이 있을 것이라고 생각하기 쉽지만 실제로는 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다. 이 중 가장 유명한 알고리즘으로 다익스트라 알고리즘이 있다.

다익스트라 알고리즘

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

DFS가 한 사람이 미로를 찾아 헤매는 과정이라면, BFS는 여러명의 사람이 각기 서로 다른 갈림길로 흩어져서 길을 찾는 것과 비슷하다고 할 수 있다. 이때 각자 실뭉치를 가지고 풀어 놓았다가 되감으면서 새로운 길을 탐색한다. 하지만 가중치가 음수인 경우에는 처리할 수 없다.

다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리 계산이 완료되었다는 확신을 가지고 더한다. 만약 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다. 이때는 모든 값을 더하여 양수로 변환하는 등의 방법을 통해 해결할 수 있으며, 이 마저도 어려울 경우에는 벨만-포드 알고리즘과 같은 음수 가중치를 계산할 수 있는 다른 알고리즘을 사용해야 한다. 이와 같은 이유로 다익스트라 알고리즘은 최장 거리를 구하는 문제에는 사용할 수 없다.

다익스트라 알고리즘을 최초로 구현했을 때에는 시간 복잡도가 O(V^2)였지만 현재는 BFS 시 가장 가까운 순서를 찾을 때 우선순위 큐를 적용하여 이 경우 시간 복잡도가 O((V+E) log V), 모든 정점이 출발지에서 도달이 가능하다면 최종적으로 O(E log V)의 시간 복잡도를 가진다.

LeetCode 743.Network Delay Time

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

Solution 1 다익스트라 알고리즘 구현

이 문제에서는 2가지 사항을 판별해야 한다.
1. 모든 노드가 신호를 받는 데 걸리는 시간
2. 모든 노드에 도달할 수 있는지 여부

모든 노드가 신호를 받을 수 있는 시간은 모든 노드가 신호를 받는 데 걸리는 시간 중 최대값이 된다. 모든 노드에 도달할 수 있는지의 여부는 방문 처리된 노드의 개수와 전체 노드의 개수를 비교하여 구할 수 있다.

우선 그래프는 인접 리스트 방식으로 구성하여 연결된 다음 노드로 빠르게 넘어갈 수 있도록 한다. 큐로 사용할 Q에는 해당 노드까지 걸리는 시간과 노드가 들어가게 된다. 이때 우선순위 큐를 사용하게 되는데 파이썬에서는 이를 heapq모듈(최소 힙)을 통해 구현한다. 이로 인해 소요 시간이 작은 순으로 Q에 삽입된다. 그리고 dist는 노드값을 키로 가지고, 걸리는 시간을 값으로 가지는 딕셔너리가 된다. 노드에 방문하면 그 노드에 대한 정보를 dist에 저장한다.

Q에 초기값으로 0, k를 넣어 시작점의 정보를 담아주고 Q가 빌때까지 반복하는 while문을 통해 Q를 순회한다. 이때 Q에 가장 앞에 담긴 노드와 연결된 노드들에 방문을 하며 Q에 연결된 노드들의 값과 소요 시간을 다시 채워주게 되고, 만약 연결된 노드가 없게되면 남아있는 Q의 노드들을 순회한 뒤에 반복문을 종료하게 된다.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        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

LeetCode 787.Cheapest Flights Within K Stops

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

Solution 1 다익스트라 알고리즘 응용

이 문제 또한 다익스트라 알고리즘을 응용한 풀이를 연습할 수 있는 좋은 문제이다. k개의 경유지 이내에 도착해야 한다는 제약사항이 하나 추가되었을 뿐, 이전에 풀었던 문제와 별 다르지 않다. 우선 다익스트라 알고리즘을 위해 우선순위 큐에 추가할 때 k이내일 때만 경로를 추가하여 k를 넘어서는 경로를 더 이상 탐색하지 않도록 작성해야 한다.

전체 노드의 비용을 모두 저장할 필요가 없기 때문에 dist 딕셔너리는 사용하지 않고, 도착점까지의 최단 경로만 계산한다.

우선 순위 큐에는 경유 횟수를 k1로 설정하여 0부터 순서대로 함께 기입한다. 이번 문제에서는 k1<=k일 경우에만 우선순위 큐에 경로를 추가하고, k를 넘게 되면 경로를 더 이상 탐색하지 않도록 해야 한다. 계속 탐색하다가 현재 노드가 도착지라면 결과를 반환하고 종료하게 되고, 큐를 끝까지 순회해도 찾지 못할 경우 도착지까지 k 이내에 도달하는 경로가 없다는 의미이므로 -1을 반환한다.

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph=collections.defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))
        Q=[(0, src, k)]
        while Q:
            price, node, k1=heapq.heappop(Q)
            if node==dst:
                return price
            if k1>=0:
                for v, w in graph[node]:
                    alt=price+w
                    heapq.heappush(Q, (alt, v, k1-1))
        return -1