최단 경로 함수 풀이 (골드4)

 

---

# 풀이

 

# 모듈 선언

 

힙 자료구조 활용과 가중치 그래프를 구현하기 위한 모듈 선언

from collections import defaultdict

import heapq

 

# 입력처리

for _ in range((E-1)):

  a, b, c = map(int, input().split())

  roads.append([a,b,c])

 

- 가중치 그래프를 2중 리스트에 저장 하였다.

 

a : 출발 정점

b : 도착 정점

c : 거리

 

- 반드시 거쳐야 하는 두 정점 처리

must_a, must_b = map(int, input().split())

- 코드 가독성을 위해 end 변수 추가

end = N

 

입력 처리 디버그

 

# 접근 방법

 

일단 다익스트라 알고리즘의 기본 형을 정의 한 뒤 수정하는 방법을 고안하기로 하였다.

 

전 내용에서 코드의 설명 부분을 상세하게 서술하며 작성하였다.

---

 

# 다익스트라 함수 정의

 

- 가중치 그래프 구현부

  graph = defaultdict(list)

  for i in roads:

    graph[i[0]].append((i[2],i[1)))

key 값 i[0] : 각 for문의 a (출발정점)

i[1] : b (도착 정점)

i[2] : c (거리)

# {

#   a : (c , b)

# }

- 가중치 그래프 구현

def dikstra(roads, end):

  graph = defaultdict(list)

  for i in roads:

    graph[i[0]].append((i[2],i[1]))

  costs = {}

  pq = []

  heapq.heappush(pq,(0,1))

  while pq:

    cur_cost, cur_node = heapq.heappop(pq)

    if cur_node not in costs:

      costs[cur_node] = cur_cost

      for cost , next_node in graph[cur_node]:

        next_cost = cost + cur_cost

        heapq.heappush(pq,(next_node,next_cost))

  return costs[end]

 

각 정점을 도착하기 위한 최소 거리를 저장할 딕셔너리 costs 

다익스트라 알고리즘의 핵심인 힙 자료구조 pq

  costs = {}

  pq = []

처음 노드 1 추가 (자기 자신이므로 거리는 0)

heapq.heappush(pq,(0,1))

 

- 힙 자료구조가 빌 때까지 (=모든 노드를 방문) 최소 비용을 costs 딕셔너리에 추가

while pq:

    cur_cost, cur_node = heapq.heappop(pq)

    if cur_node not in costs:

      costs[cur_node] = cur_cost

      for cost , next_node in graph[cur_node]:

        next_cost = cost + cur_cost

        heapq.heappush(pq,(next_node,next_cost))

- 도착지 노드의 최소 거리 출력

return costs[end]

 

- 출력

 

---