[Baekjoon, Python] 1753번 : 최단경로

도입

백준 단계별 풀기 최단경로 첫 번째 문제이다.

백준 1753번 문제, 입력, 출력

---

백준 1753번 입출력 예제 1

---

다익스트라 알고리즘 [출처 : 위키 백과]

---

풀이

1. 다익스트라 알고리즘 사용할 것이다. dijkstra 라는 함수를 정의하고, 매개변수로 시작점(var_start)을 받는다. 

 

2.  heapq 라이브러리를 사용한다. heap에는 방문할 vertex의 정보들이 들어있다. [최단거리, vertex]로 구성이 되어 있다. 

 

3. mat_table은 vertex간 어떻게 연결되어 있는지 인덱스값을 그 값에 해당하는 vertex(var_u)라고 두고, 해당 vertex에 연결된 다른 vertex(var_v)와 가중치(var_w) 정보를 넣어둔다.

 

4. list_shortest_dist는 시작점 index를 제외한 다른 index 들의 값을 INF(무한:infinite이란 뜻)으로 초기화 한다.

 

5. heap의 vertex를 꺼내서 mat_table에 vertex와 연결된 다른 vertex의 weight을 더해주고(now_w) 현재 lilst_shortest_dist에 저장되어 있는 값과 비교해서 저장되어 있는 값보다 크다면 PASS, 작다면 list_shortest_dist[now_v]값을 업데이트 한다. 

---

코드

from sys import stdin
from heapq import heappush, heappop
INF = 1e7

def dijkstra(var_start):
    list_shortest_dist[var_start] = 0
    heappush(heap, [0, var_start])
    while heap:
        vtx_w, vtx_v = heappop(heap)
        for now_v, wei in mat_table[vtx_v]:
            now_w = wei + vtx_w
            if now_w < list_shortest_dist[now_v]:
                list_shortest_dist[now_v] = now_w
                heappush(heap, [now_w, now_v])

var_V,var_E = map(int, stdin.readline().split())
var_start = int(stdin.readline())
mat_table = [[] for i in range(var_V+1)]     # [[], [], [], []]
list_shortest_dist = [INF] * (var_V + 1) # [10000000.0, 10000000.0, 10000000.0, 10000000.0, 10000000.0, 10000000.0]
heap = []

for _ in range(var_E):
    var_u,var_v,var_w = map(int, stdin.readline().split())
    mat_table[var_u].append([var_v,var_w])

dijkstra(var_start)

for i in list_shortest_dist[1:]:
    print(i if i != INF else "INF")

---

마무리

다익스트라 알고리즘을 알고 푸는 것이 좋다. 

 

피드백은 언제나 환영이다^.^