[Baekjoon, Python] 1504번 : 특정한 최단 경로

도입

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

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

---

백준 1504번 입출력 예제 1

---

풀이

1. 다익스트라 알고리즘을 사용한다. def dijkstra 함수를 정의하고, 매개변수로 start 할 꼭짓점을 받는다.

 

2. 그래프 정보를 가지는 변수(mat_table)를 선언한다. 단방향이 아닌, 양방향이기 때문에, 두 줄에 걸쳐서 넣어준다(윗 그림). 다음은 예제1의 입력이 주어졌을 때, 실제 만들어지는 mat_table 이다(아랫 그림). 

양방향 그래프를 만들기 위한 코드

예제1의 입력이 주어졌을 때, 실제 만들어지는 mat_table 

3. 출발 꼭짓점으로 부터 해당 꼭짓점 까지의 weight값을 저장할 변수(list_shortest_dist)를 dijkstra함수 내부에 선언을 하고, 해당 변수를 return 하게 한다. 

 

4. 1, v1, v2 지점을 dijkstra 함수의 매개변수로 주고, 그것에 맞는 list_shortest_dist를 리턴 받는다. 

1,v1,v2를 시작점으로 하는 list_shortest_dist

5. 1-v1-v2-N, 1-v2-v1-N 이 두 가지의 경로의 최단거리를 계산해서 min값을 채택한다.

---

코드

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

def dijkstra(var_start):
    list_shortest_dist = [INF] * (var_N + 1)
    list_shortest_dist[var_start] = 0
    heappush(heap, [0, var_start])
    while heap:                                                                                 
        pre_w, vtx_v = heappop(heap)                                                           
        for now_v, vtx_w in mat_table[vtx_v]:  #해당 vtx_v에 연결된 vertex들의 정보 꺼내옴        
            now_w = vtx_w + pre_w                                                              
            if now_w < list_shortest_dist[now_v]:
                list_shortest_dist[now_v] = now_w
                heappush(heap, [now_w, now_v])
    return list_shortest_dist

var_N,var_E = map(int, stdin.readline().split())  
mat_table = [[] for i in range(var_N+1)]       
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])
    mat_table[var_v].append([var_u,var_w])

var_v1, var_v2 = map(int, stdin.readline().split())

ls_start = dijkstra(1)     
ls_v1 = dijkstra(var_v1)   
ls_v2 = dijkstra(var_v2)

shortest_dist = min(ls_start[var_v1] + ls_v1[var_v2] + ls_v2[var_N], ls_start[var_v2] + ls_v2[var_v1] + ls_v1[var_N])
print(shortest_dist if shortest_dist < INF else -1)

---

마무리

다익스트라 알고리즘에 대한 공부가 필요한 문제였다.