[알고리즘 분석 #5] 1916 최소비용구하기 (파이썬)

알고리즘

다익스트라 알고리즘

BFS랑 구조가 비슷하다.

단, 해당 문제는 "비용" 이 들어가기 때문에

graph: 그래프의 간선을 저장하는 2차원 배열

costs: index 위치의 최소비용 저장 1차원 배열

2가지가 필요하다

 

BFS와 차이점은 방문여부를 따로 관리하지 않는다

이를 비용이 저장되있는것보다 더 크면, continue함으로써 비용 절약을 한다.

이를 통과하면 graph 배열을 통해 갈수있는 간선을 확인하고, 거쳐서 가는 비용이 더 적다면 갱신하고 q에 넣는다

 

기본 코드

import heapq  # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # queue에 남아 있는 노드가 없으면 끝
    current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.

    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
      continue
    
    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
      if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    
  return distances

출처: https://justkode.kr/algorithm/python-dijkstra

 

 

자료구조

최소힙 ( heapq )

파이썬 기몬 모듈로 지원한다

import heapq

최소힙은 최소값, 최대값의 연산을 빠르게 하도록 도와주는 자료구조이다.

이진트리로 이루어져 있고, 이는 이후 세그먼트 트리와도 연관있으니 살짝 정리해보자

 

최소힙: 부모노드 < 자식노드

최대힙: 부모노드 > 자식노드

 

최소힙은 작으면 더 우선순위가 높아 부모로 있다

최대힙은 크면 더 우선순위가 높아 부모로 있다

 

원소가 값만 들어가 있다면 1차원 배열로 저장하여 ~번째로 큰수나 작은수를 구할 수 있을 것 같다

https://batory.tistory.com/1

힙을 사용해 K번째로 큰 수 구하기

 

코드

import sys, heapq
input = sys.stdin.readline # 안하면 시간 초과


n = int(input())
m = int(input())
INF = sys.maxsize
graph = [[] for _ in range(n+1)]
costs = [INF] * (n+1)

for _ in range(m):
    a, b, w = map(int, input().split())
    graph[a].append([w,b])
start, end = map(int, input().split())
costs[start] = 0
costs[0] = 0
q = list()
heapq.heappush(q, [0, start])

while q:
    w0, x0 = heapq.heappop(q)

    if w0 > costs[x0]: # 안하면 시간 초과
        continue

    for w1, x1 in graph[x0]:
        w2 = w1 + w0 # 갱신 하는 값
        if w2 >= costs[x1]: continue
        costs[x1] = w2
        heapq.heappush(q, [w2, x1])


print(costs[end])