[Baekjoon Online Judge] 백준 1504번 특정한 최단 경로(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1504번 특정한 최단 경로

(Python)

(글쓴날 : 2020.06.11)

 

---

* Baekjoon Online Judge, 백준 1504번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1504번 특정한 최단 경로

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

2) 풀이 과정

* 시간 복잡도 : O(E log V)

 

주어지는 무향 그래프의 1번 정점에서 N번 정점으로 이동할 때, 임의의 주어진 두 정점을 반드시 통과하는 최소 거리를 구하는 문제입니다.

단, 경로가 없을 시 -1을 출력합니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보를 인접 리스트로 구현한 뒤, 반드시 통과해야 하는 정점을 고려해 만든 두 가지 경로(V1을 먼저 방문하는 경로, V2를 먼저 방문하는 경로)에 다익스트라를 적용하였고, 각 경로에서 다익스트라로 구한 구간마다의 값들을 더해가며 경로별 총 최솟값을 구했습니다.

마지막으로, 불가능한 경로를 제외한 두 가지 경로 중 최솟값을 구하여 문제를 해결했습니다.

 

밑의 제 코드의 경우, PyPy3로 제출하여야 시간 초과가 발생하지 않습니다.

---

3) 코드

 

* Python 코드(PyPy3)

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq):
    while hq:
        wei, vec = heapq.heappop(hq)
        
        if di[vec] > wei:
            di[vec] = wei
 
            for w, v in adjList[vec]:
                heapq.heappush(hq, (w+wei, v))
 
N, E = map(int,input().split())
 
ans = [0, 0]
 
INF = 2147483647
adjList = [[] for _ in range(N+1)]
 
for _ in range(E):
    a, b, c = map(int,input().split())
 
    adjList[a].append((c,b))
    adjList[b].append((c,a))
 
stopOver = list(map(int,input().split()))
itinerary = [[1,stopOver[0],stopOver[1],N], [1,stopOver[1],stopOver[0],N]]
 
for i in range(2):
    for j in range(3):
        di = [INF] * (N+1)
        di[itinerary[i][j]] = 0
        hq = []
        for w, v in adjList[itinerary[i][j]]:
            heapq.heappush(hq,(w,v))
        BFS(hq)
        ans[i] += di[itinerary[i][j+1]]
 
print(min(ans) if min(ans) < INF else -1)

---