[BOJ 1753] 최단경로(Python)

문제

최단 경로

문제 해설

이 문제는 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제이다.

다익스트라 알고리즘이란

최단 경로를 찾을 때 사용하는 알고리즘으로 구현 방법에 따라 O(V^2) 혹은 O(VlogE)의 시간복잡도를 가지는 알고리즘이다. (V = 노드의 수 E = 간선의 수) 원리는 다음과 같다.

1. 출발 노드를 설정
2. 최단 거리를 가지는 리스트를 만들고, 모두 정수 최대 값으로 초기화한다.(단, 출발 노드는 거리가 0)
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. -반복
4. 원래 들어있던 최단 거리와 현재노드가 가지고 있는 가중치를 비교 후 갱신한다. -반복

각 단계를 거칠때 마다 하나의 노드가 최단거리를 확정적으로 결정 짓는다고 생각하면 될 것 같다. 위 단계에서 모든 노드(V)에 대해 최단 거리가 가장 짧은 노드를 선형 탐색(V) 하므로 시간 복잡도는 O(V^2)가 소모된다.

또 다른 방법은 우선순위 큐를 이용하는 것이다. heapq를 이용해 우선순위 큐를 만들고 우선순위에 해당하는 곳에 가중치와 해당 노드를 튜플로 묶어 저장한다. 이렇게 하면 굳이 가장 짧은 노드를 탐색할 필요가 없고(V) push, pop만 하면 되므로(logE) 시간복잡도가 훨씬 줄어든다. 선형 탐색할 시간이 우선순위 큐에서 push, pop하는 시간으로 대체되는 것이다.(VlogE)

시간이 많이 소요되는 코드 (O(V^2))

# 4:00
import sys

input = sys.stdin.readline
inf = float("INF")  # 무한값
v, e = map(int, input().split())  # 노드, 간선 개수
start = int(input())  # 시작 노드
visited = [False] * (v + 1)  # 방문 체크 리스트
graph = [[] for _ in range(v + 1)]  # 연결 정보
value_table = [inf] * (v + 1)  # 가중치 테이블 초기화
value_table[start] = 0  # 시작점 초기화

for i in range(e):
    a, b, c = map(int, input().split())  # 연결정보, 가중치
    graph[a].append((b, c))


# 방문하지 않은 노드 중 가중치가 가장 낮은것을 고름
def find_node():
    node, min_value = 0, inf
    for i in range(1, v + 1):
        if not visited[i] and min_value > value_table[i]:
            node, min_value = i, value_table[i]
    return node


for _ in range(v):
    now = find_node()
    distance = value_table[now]  # 현 노드의 가중치
    for goal, value in graph[now]:
        # 저장되있는 최단거리보다 짧을경우
        if value_table[goal] > distance + value:
            value_table[goal] = distance + value
    visited[now] = True

for i in range(1, v + 1):
    if value_table[i] == inf:
        print("INF")
    else:
        print(value_table[i])

시간이 조금 소요되는 코드 (O(ElogV))

# 9:47
import heapq
import sys

input = sys.stdin.readline

v, e = map(int, input().split())  # 정점, 간선
start = int(input())  # 시작점

inf = float("INF")
graph = [[] for _ in range(v + 1)]  # 연결 정보 (이어진 곳, 가중치) 튜플
pq = []  # 우선순위 큐, heapq로 사용됨 (파이썬은 최소 힙을 기본으로 구현되어있음)
value_table = [inf] * (v + 1)  # 가중치 테이블
value_table[start] = 0
heapq.heappush(pq, (0, start))

for i in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))  # a번째 리스트에 (목적지, 가중치) 저장

while pq:
    weight, node = heapq.heappop(pq)  # 최소 힙에서 pop
    if value_table[node] < weight:  # 한번 처리된 적이 있는 노드는 continue
        continue                    # 왜냐면, 큐에 있던 노드의 가중치는 갱신 안되어있음
    for goal, value in graph[node]:
        if value_table[goal] > weight + value:
            value_table[goal] = weight + value
            heapq.heappush(pq, (weight + value, goal))

for i in range(1, v + 1):
    if value_table[i] == inf:
        print("INF")
    else:
        print(value_table[i])