[BOJ] 1753 - 최단경로

풀어보기

접근

문제를 풀 때까지만 해도 필자는 다익스트라 알고리즘의 세부 구현을 몰랐다...
그래서 가중치를 반영하는 DFS를 생각해봤다.

코드 1 - 순진하게 완전 탐색

from sys import stdin


V, E = map(int, stdin.readline().strip().split())
start_node = int(stdin.readline())

# {i: {next: weight}}
graph = {i + 1: {} for i in range(V)}

for _ in range(E):
    u, v, w = map(int, stdin.readline().strip().split())

    if v not in graph[u].keys():
        graph[u][v] = w

    # 최솟값을 가지는 간선만 포함
    else:
        graph[u][v] = min(graph[u][v], w)    




def search(current_node: int, destination: int, visited: list[bool], weights: int):
    global min_weights

    if current_node == destination:
        min_weights = min(min_weights, weights)
        return weights

    for next_node in graph[current_node]:
        if visited[next_node]:
            continue

        visited[next_node] = True
        search(next_node, destination, visited, weights + graph[current_node][next_node])
        visited[next_node] = False
    
    return


for i in range(V):
    min_weights = 10 * 300_000 + 1
    search(start_node, i + 1, [False] * V, 0)
    print(min_weights if min_weights != 10 * 300_000 + 1 else "INF")

전역 변수인 min_weights를 각 탐색마다 초기화한 다음 깊이 우선 탐색을 진행하며 최솟값을 업데이트 방법을 생각해봤다. 가능한 간선 수가 30만개 정도 되므로 당연히 시간 초과가 났다.

그렇다면 지금껏 발견했던 출발점으로부터 각 노드까지의 최단 거리를 기록해가며 탐색을 진행해보자는 생각을 했고, 다음 노드의 탐색도 이 최단 거리보다 작은 경우에만 탐색을 진행하도록 코드를 수정했다.

코드 2 - 각 노드까지의 최단 거리를 기록하며 탐색

from sys import stdin


V, E = map(int, stdin.readline().strip().split())
start_node = int(stdin.readline())

# {i: {next: weight}}
graph = {i + 1: {} for i in range(V)}

for _ in range(E):
    u, v, w = map(int, stdin.readline().strip().split())

    if v not in graph[u].keys():
        graph[u][v] = w

    # 최솟값을 가지는 간선만 포함
    else:
        graph[u][v] = min(graph[u][v], w)    


def search():
    visited = [False] * (V + 1)
    # 현재까지 발견한 최단 거리를 저장하는 배열
    distances = [10 * 300_000 + 1 for _ in range(V + 1)]
    distances[start_node] = 0

    visit_count = 0
    current_node = start_node

    while visit_count < V:
        # 탐색할 노드 정하기
        min_distance = 10 * 300_000 + 1
        for node in graph:
            if not visited[node] and distances[node] < min_distance:
                min_distance = distances[node]
                current_node = node

        visited[current_node] = True
        
        for next_node in graph[current_node]:
            calculated_distance = distances[current_node] + graph[current_node][next_node]

            if calculated_distance < distances[next_node]:
                distances[next_node] = calculated_distance

        visit_count += 1

    return distances


distances = search()

for d in distances[1:]:
    print(d if d != 10 * 300_000 + 1 else "INF")

여전히 시간 초과를 벗어나지는 못했다. 이쯤까지 해 두고 다익스트라 알고리즘을 찾아보기 시작했다...

코드 3 - 다익스트라 알고리즘

from sys import stdin
import heapq

V, E = map(int, stdin.readline().strip().split())
start_node = int(stdin.readline())

# {i: {next: weight}}
graph = {i + 1: {} for i in range(V)}

for _ in range(E):
    u, v, w = map(int, stdin.readline().strip().split())

    if v not in graph[u].keys():
        graph[u][v] = w

    # 최솟값을 가지는 간선만 포함
    else:
        graph[u][v] = min(graph[u][v], w)    


def search():
    visited = [False] * (V + 1)
    # 현재까지 발견한 최단 거리를 저장하는 배열
    distances = [10 * 300_000 + 1 for _ in range(V + 1)]
    distances[start_node] = 0

    visit_count = 0
    current_node = start_node

    while visit_count < V:
        # 탐색할 노드 정하기
        min_distance = 10 * 300_000 + 1
        for node in graph:
            if not visited[node] and distances[node] < min_distance:
                min_distance = distances[node]
                current_node = node

        visited[current_node] = True
        
        for next_node in graph[current_node]:
            calculated_distance = distances[current_node] + graph[current_node][next_node]

            if calculated_distance < distances[next_node]:
                distances[next_node] = calculated_distance

        visit_count += 1

    return distances


def search():
    distances = [10 * 300_000 + 1 for _ in range(V + 1)]
    distances[start_node] = 0

    queue = [(0, start_node)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        # 지금껏 봤던 최단 경로보다 긴 경우 또 탐색할 필요가 없음
        if distances[current_node] < current_distance:
            continue

        # 현재 노드에서 갈 수 있는 다음 노드 탐색
        for next_node in graph[current_node]:
            distance = current_distance + graph[current_node][next_node]

            # 지금껏 봤던 최단 경로보다 더 짧은 놈 발견
            if distance < distances[next_node]:
                distances[next_node] = distance
                heapq.heappush(queue, (distance, next_node))

    return distances


distances = search()

for d in distances[1:]:
    print(d if d != 10 * 300_000 + 1 else "INF")

코드 2와의 차이는 다음 노드를 탐색할 때 우선 순위 큐(=힙)를 쓴다는 것이다. 최소 거리를 가지는 다음 노드를 우선적으로 탐색하게 되어 $O(n\log n)$ 시간 정도에 탐색을 끝낼 수가 있게 되었다.

다익스트라 알고리즘

• 가중치가 있는 그래프에서 한 노드로부터 다른 모든 노드까지의 최소 가중치를 가지는 경로를 찾고자 할 때 쓴다.

• 현재 탐색 대상인 노드에서 그 다음 노드를 탐색할 때, 현재까지 찾았던 최단 경로보다 더 짧은 경우에만 탐색을 진행한다.

• 이 때 다음 탐색 대상 노드를 우선 순위 큐에 담는다면 $O(n \log n)$의 시간복잡도를 가지고, 코드 2처럼 선형 탐색으로 진행한다면 $O(n^2)$의 시간복잡도를 가진다.