[알고리즘] BOJ 1504 특정한 최단 경로 #Python

[BOJ] 1504 특정한 최단 경로 바로가기

📍 문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

---

📍 입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

---

📍 출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

---

📍 풀이

🧷 풀이 과정

1번 정점에서 N번 정점까지 최단 거리로 이동하는데 임의로 주어진 두 정점을 반드시 통과해야 하는 조건을 만족하는 이동 경로는 다음 2가지 방법이다.

[case1] : 1 → u → v → N
[case2] : 1 → v → u → N

최단 거리를 구하는 방법인 다익스트라(Dijkstra) 알고리즘을 이용하여 문제를 해결하였다.

정점 1 에서 u로 이동하는 최단 거리를 다익스트라 알고리즘을 통해 구하고,
정점 u 에서 v로 이동하는 최단 거리를 다익스트라 알고리즘을 통해 구하고,
정점 v 에서 N로 이동하는 최단 거리를 다익스트라 알고리즘을 통해 구한다.

위에서 구한 최단 거리를 모두 더하면 [case1]에 해당하는 이동 경로의 최단 거리를 구할 수 있다.

[case2]에 해당하는 이동 경로도 이와 같은 방법을 이용하여 구한다.

만약 [case1] 와 [case2]의 이동경로가 모두 존재하지 않는다면 -1을 반환하고,
이동 경로가 존재한다면 min() 함수를 통해 최단 거리를 반환한다.

✍ 전체 코드

# BOJ 1504 특정한 최단 경로
# https://www.acmicpc.net/problem/1504

from sys import stdin, maxsize
from heapq import heappop, heappush
from collections import defaultdict

def solution(N, E, edges, u, v):
    
    # graph init
    graph = defaultdict(list)
    for a, b, c in edges:
        graph[a].append((b,c))
        graph[b].append((a,c))

    # dijkstra
    def dijkstra(u, v):
        result = [maxsize] * (N+1)
        result[u] = 0
        heap = [(0,u)]
        while heap:
            weight, node = heappop(heap)
            for nextNode, nextWeight in graph[node]:
                if result[nextNode] > weight + nextWeight:
                    result[nextNode] = weight + nextWeight
                    heappush(heap, (weight+nextWeight, nextNode))
        return result[v]
    
    # [case1] : 1 → u → v → N
    case1 = dijkstra(1,u) + dijkstra(u,v) + dijkstra(v,N)
    # [case2] : 1 → v → u → N
    case2 = dijkstra(1,v) + dijkstra(v,u) + dijkstra(u,N)
    
    return -1 if case1 >= maxsize and case2 >= maxsize else min(case1, case2)

N, E = map(int,stdin.readline().split())
edges = list(list(map(int,stdin.readline().split())) for _ in range(E))
u, v = map(int,stdin.readline().split())

result = solution(N, E, edges, u, v)
print(result)