백준 1753 최단경로

백준 1753번 최단경로 문제를 풀어보겠습니다.

파이썬!

from heapq import heappush, heappop

N, M = map(int,input().split())

start_node = int(input())

graph = { i : [] for i in range(1, N+1)}

for _ in range(M):
    a, b, c = map(int, input().split(' '))
    graph[a].append((b, c))


INF = int(1e9)

distance = [INF for _ in range(N+1)]

def dijkstra(start):
  distance[start] = 0
  queue = []
  queue.append([0, start])
  while queue:
    dist, node = heappop(queue)
    for destination, cost in graph[node]:
      if distance[destination] > dist + cost:
        distance[destination] = dist + cost
        heappush(queue, [dist + cost, destination])

dijkstra(start_node)

for i in range(1, N+1):
  if distance[i] == INF:
    print('INF')
  else:
    print(distance[i])

이 문제는 경로마다 cost가 존재하고 cost를 최소화하는 경로를 찾는 문제입니다.
이렇게 경로가 있고 경로에 cost가 있다면 다익스트라 알고리즘 혹은 플루이드 워셜 알고리즘을 이용하죠!!

이 문제는 최종적으로 start 노드에서 다른 각 노드까지의 최단거리를 표현하면 되기 때문에 다익스트라 알고리즘을 활용했습니다.

다익스트라 알고리즘은 우선순위 큐를 활용한 알고리즘 입니다.
파이썬에서는 이것이 heapq라는 모듈로 구현이 가능합니다.

우선순위 큐

큐에 정보를 저장할때 자동으로 정렬을 해주는 큐입니다. 따라서 매순간 큐에서 자료를 꺼낼때마다 가장 작은 cost가 사용되는 경로를 추출할 수 있게 도와주는거죠!

그러면 리스트를 통해서 매번 탐색하는 것과 얼마나 시간차이가 날까?

리스트는 탐색, 추출 or 삽입 과정에서 각각 N의 시간복잡도로 최종적으로는 O(N^2)이 걸리게 된다..

우선순위 큐를 사용하면 힙에 넣는 과정에서 logN, 힙에서 빼는 과정에서도 logN 의 시간 복잡도를 가지고 있기 때문에 월등하게 빠르므로 우선순위 큐를 사용하자!

from heapq import heappush, heappop

다익스트라 알고리즘

• 이 알고리즘은 우선순위 큐를 활용해서 while 반복문을 시행하게 됩니다.

1. 우선 distance 리스트로 출발 노드 부터 각 노드 까지의 거리를 표현해줍니다.

2. 큐를 활용하여 반복문을 돌려주면서 distance에 내장되어 있는 cost 값과 현재 큐에 있는 정보와 비교를 해봅니다.

3. 이때 더 작은 값이 나온다면 distance 리스트의 cost 값을 업데이트 해주고 우선순위 큐에 [cost, 출발노드] 를 heappush 를 통해서 넣어줍니다!

4. 최종적으로 반복문이 끝나면 distance 리스트에는 출발노드로 부터 각 노드로의 최소 경로만이 남게됩니다.