1916 파이썬1 [알고리즘 분석 #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로 부터의 거리 값을.. 2023. 2. 23. 이전 1 다음
