Dijkstra 알고리즘 문제 유형

Dijkstra 알고리즘은 최단 경로를 찾기 위한 알고리즘으로써, 특정 노드에서 다른 노드로의 최단 경로를 찾는 문제에서 사용된다.

(모든 노드에서 다른 노드로의 최단 경로를 찾기 위해서는 Floyd Warshall 알고리즘을 사용해야한다)

 

이번 포스팅에서는 Dijkstra 알고리즘을 활용하는 문제의 유형에 대해 알아보도록 하겠다.

(참고: Dijkstra 알고리즘 자체에 대해서는 다루지 않는다)

---

모든 노드로의 최소 경로 찾기

• Network Delay Time

Dijkstra 알고리즘 문제 중 가장 기본적인 유형으로, 이 문제를 풀기 위해서는 시작 노드에서 모든 노드로의 최단 경로를 알아야 한다.

 

추가적으로 이 문제에서는 모든 노드가 연결되지 않은 경우에 대해서도 다루고 있다.

이는 각 노드로의 최소 거리를 확인하면 되므로 쉽게 해결할 수 있다. (36~38 라인)

import math
from queue import PriorityQueue

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n+1)]
        for a, b, time in times:
            graph[a].append((b, time)) # 단방향
            # graph[b].append((a, time)) # 양방향 문제라면 추가

        # 시작 노드 k에서 각 노드로의 최소 거리
        min_times = [math.inf] * (n+1)
        min_times[k] = 0

        q = PriorityQueue()
        q.put((0, k))
        
        while q.queue:
            curr_time, curr_node = q.get()

            # 더 짧은 경로를 이미 발견한 경우
            # curr_node와 연결된 노드들은 기존에 발견한 더 짧은 경로를 사용한다
            if min_times[curr_node] < curr_time:
                continue
            
            for next_node, next_time in graph[curr_node]:
                total_time = curr_time + next_time

                if total_time < min_times[next_node]:
                    min_times[next_node] = total_time
                    # 다음 탐색할 노드가 출발 노드와의 거리 오름차순으로 정렬됨
                    q.put((total_time, next_node))

        time_to_spread = max(min_times[1:])
        
        # 연결이 안된 노드가 있는지 확인
        if time_to_spread == math.inf:
            return -1

        return time_to_spread

 

탐색 우선 순위를 위한 PriorityQueue

Dijkstra 알고리즘과 관련하여 잘 알아야 할 것이 위 코드의 32번째 라인에서 다음에 탐색할 노드를 PriorityQueue에 추가할 때 tuple의 0번째 원소 값인데,

PriorityQueue는 지금과 같이 0번째 원소가 숫자인 tuple을 추가하면 해당 tuple의 0번째 숫자값이 작을 수록 우선 순위가 높다.

from queue import PriorityQueue

q = PriorityQueue()

q.put((1, "one"))
q.put((4, "four"))
q.put((2, "two"))

q.get() # (1, "one")
q.get() # (2, "two")
q.get() # (4, "four")

 

그렇기에 "최단 경로"를 찾는 경우에는 다음 노드를 추가할 때 양수의 거리를 tuple의 첫번째 원소로 넣어주어야 가장 가까운 경로를 먼저 탐색할 수 있게된다.

반대로 "최대 경로"를 찾는 경우에는 가장 먼 경로를 먼저 탐색해줘야하기 때문에, 음수의 거리를 tuple의 첫번째 원소로 넣어주어야 한다.

('최대 경로 찾기' 유형에서 다시 언급하도록 하겠다)

 

특정 노드로의 최소 경로 찾기

• 최소비용 구하기

이 유형과 이전 유형과의 차이는 '도착 노드가 정해져 있다는 것'이다.

문제 풀이 자체는 이전 유형과 동일하게 하여도 결과는 같으나, if 문을 추가하여(24~26 라인) 추가적인 iteration을 막아줄 수 있다.

(도착 노드에 대한 최소 경로만 찾으면 되는데, 불필요하게 거리가 더 먼 다른 노드를 경유하면서 경로를 찾을 필요는 없다)

 

때로는 이 처리로 인해서 시간 제한 내에 문제가 풀리기도 한다.

from queue import PriorityQueue
import math

def solution(N, M, times, A, B):
    graph = [[] for _ in range(N+1)]
    for a, b, time in times:
        graph[a].append((b, time)) # 단방향

    # 시작 노드 A에서 각 노드로의 최소 거리
    min_times = [math.inf] * (N+1)
    min_times[A] = 0

    q = PriorityQueue()
    q.put((0, A))

    while q.queue:
        curr_time, curr_node = q.get()

        # 더 짧은 경로를 이미 발견한 경우
        # curr_node와 연결된 노드들은 기존에 발견한 더 짧은 경로를 사용한다
        if min_times[curr_node] < curr_time:
            continue
        
        # 출발 노드에서 도착 노드까지 거리가 최소인 경우가 먼저 조회되기 때문에 바로 return 한다.
        if curr_node == B:
            return curr_time

        for next_node, next_time in graph[curr_node]:
            total_time = curr_time + next_time
            
            if total_time < min_times[next_node]:
                min_times[next_node] = total_time
                q.put((total_time, next_node))

    raise ValueError("시작노드에서 도착노드까지 연결되지 않았습니다.")

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
times = [list(map(int, input().split())) for _ in range(M)]
A, B = list(map(int, input().split()))
print(solution(N, M, times, A, B))

 

최대 경로 찾기

• Path with Maximum Probability

최대 경로를 찾는 문제의 경우 최소 경로를 찾는 문제와 반대로 처리하면 풀 수 있다.

• 값을 비교할 때의 부등호의 방향
  • 최소가 아니라 최대를 찾는 문제이기 때문에 부등호를 반대로 한다.
• PriorityQueue에 추가하는 값의 부호
  • 앞서 '탐색 우선 순위를 위한 PriorityQueue' 에서 언급했던 것 처럼, 최대 경로를 찾을 때는 PriorityQueue에 넣는 prioirty 값의 부호도 달라져야한다.

 

이 문제는 앞서 특정 노드로의 최소 경로를 찾는 유형의 문제이기도 하다.

추가적으로 이 문제는 최대 확률을 구하는 문제이기 때문에 경로를 지나면서 확률 값을 계속 곱해줘야하기 때문에 조금 머리를 더 써야하는 문제이기도 하다.

from queue import PriorityQueue

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        graph = [[] for _ in range(n)]
        for (a, b), prob in zip(edges, succProb):
            graph[a].append((b, prob))
            graph[b].append((a, prob)) # 양방향

        max_probs = [-1] * n
        max_probs[start_node] = 1 # 다음 노드의 도착 확률과 곱해야하기 때문에 출발 노드의 도착 확률은 1

        q = PriorityQueue()
        q.put((-1, start_node))

        while q.queue:
            curr_prob, curr_node = q.get()
            curr_prob *= -1 # 우선순위를 높이기 위해 음수를 넣었기에 다시 양수로 바꾼다

			# 더 높은 확률의 경로를 이미 발견한 경우
            if curr_prob < max_probs[curr_node]:
                continue

            # 도착 노드 차례인 경우 바로 return 한다
            if curr_node == end_node:
                return curr_prob

            for next_node, next_prob in graph[curr_node]:
                total_prob = curr_prob * next_prob
                
                if max_probs[next_node] < total_prob:
                    max_probs[next_node] = total_prob
                    # 최대 경로를 구하는 문제이기 때문에 큰 값이 더 높은 우선순위를 가져야하므로 0번째 원소를 음수값을 넣는다.
                    q.put((-total_prob, next_node))

        # 시작 노드와 도착 노드가 연결되어있지 않은 경우
        return 0