[BOJ] 1504번 특정한 최단 경로 / 사용언어 : 파이썬(python)

※ 문제링크 

1504번: 특정한 최단 경로

※ 관련개념

23. 다익스트라(Dijkstra) 알고리즘

해당 문제는 가중치가 있는 최단거리 계산 문제로 다익스트라 알고리즘을 활용해서 풀 수 있는 문제였다. 다익스트라 알고리즘을 파이썬에서 구현하기 위해 heapq를 사용하여 우선순위 큐 자료구조를 구현하였고, 메모이제이션 개념과 그래프 구현을 위해 딕셔너리와 리스트 자료구조를 활용하였다. 풀이방법 자체는 생각보다 쉽게 떠올렸으나 구현과정에서 조금 애를 먹었던 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 리스트를 활용하여 그래프를 구현해준다.(양방향 그래프를 고려)

2.  heapq와 메모이제이션 개념을 활용하여 다익스트라 알고리즘을 구현해준다.

3. 문제조건에서 2개의 정점을 거쳐서 간다했으므로 각각의 정점에서의 다른 정점으로의 최단거리를 계산 후 딕셔너리에 저장한다.

4. 조건상 나올 수 있는 조합은 1 -> cp1 -> cp2 -> N or 1 -> cp2 -> cp1 -> N이 가능하다. 2가지 경우의 값들을 구한다.

5. 만약 두 경우 모두 inf면 -1을 그렇지 않으면 가장 작은 값을 출력한다.

+ 입력값이 많아 sys를 사용하였으며, 사용시에는 개행문자에 유의하도록 하자.

 

import heapq
import sys

# input = sys.stdin.readline
inf = float('inf')
N, E = map(int, input().split()) # N: 정점의 개수 / E: 간선의 개수
graph = [[] for _ in range(N+1)]
for _ in range(E):
    a, b, c = map(int, input().split()) # a, b: 각 정점 / c: 정점사이의 거리(양방향)
    graph[a].append([c, b])
    graph[b].append([c, a])
cp1, cp2 = map(int, input().split())

def dijkstra(start):
    heap = []
    dp = [inf for _ in range(N+1)]
    for ele in graph[start]:
        heapq.heappush(heap, ele)
        dp[ele[1]] = ele[0] 
    dp[start] = 0

    while heap:
        sample = heapq.heappop(heap)
        wei, p = sample[0], sample[1]
        for ele in graph[p]:
            if wei + ele[0] < dp[ele[1]]:
                dp[ele[1]] = wei + ele[0]
                heapq.heappush(heap, [dp[ele[1]], ele[1]])
    return dp

dp_dic = dict()
cb = [[1, cp1, cp2, N], [1, cp2, cp1, N]]
for point in cb[0]:
    if point not in dp_dic:
        dp_dic[point] = dijkstra(point)
ans = inf
for point_list in cb:
    cnt = 0
    for i in range(len(point_list)-1):
        cnt += dp_dic[point_list[i]][point_list[i+1]]
    if cnt < ans:
        ans = cnt
if ans == float('inf'):
    print(-1)
else:
    print(ans)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.