[백준] 1504 특정한 최단 경로 (파이썬)

골드 Ⅳ

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

📄 문제

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

 

1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

---

💡 아이디어

• 1번 정점에서 N번 정점으로 최단 거리로 이동해야 하므로 다익스트라 알고리즘을 사용한다.
• 그런데, 두 개의 서로 다른 정점 v1과 v2를 지나야 한다.
• 1번에서 N번으로 가는데 v1과 v2를 지나는 방법은 2가지 존재한다.
  1. 1 → v1 → v2 → N
  2. 1 → v2 → v1 → N
• 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 알려준다.
• 따라서, 시작점을 1, v1, v2의 3가지 경우로 나누어 다익스트라 알고리즘을 수행하면 필요한 최단 거리를 모두 알 수 있다.
• 1 → v1 → v2 → N과 1 → v2 → v1 → N, 두 경우를 비교하여 최단거리를 출력한다.
• 최단 거리가 설정한 최댓값 보다 크거나 같으면   해당 경로가 없으므로 -1을 출력한다.

 

📝 문제 풀이 (Code)

import sys, heapq
input = sys.stdin.readline

# start에서 각 점까지의 최단거리
def dijkstra(start):
    # 모든 정점사이의 거리를 최댓값으로 초기화
    # 최단 거리 저장
    visited = [INF]*(n+1)
    heap = []
    # 최단거리, 시작 위치 저장
    heapq.heappush(heap, (0, start))
    visited[start] = 0
    while heap:
        # start부터 현재 위치까지 최단거리, 현재 위치
        dist, v = heapq.heappop(heap)

        # 현재 위치까지 거리보다 이미 저장된 거리가 짧으면
        # 해당 경우는 탐색하지 않는다.
        if visited[v] < dist:
            continue
        # 다음 위치, 다음 위치까지 거리
        for w, nextDist in graph[v]:
            totalDist = dist + nextDist
            # 새로 구한 거리가 저장된 거리보다 짧으면 갱신
            if totalDist < visited[w]:
                visited[w] = totalDist
                heapq.heappush(heap, (totalDist, w))
    # start부터 저장된 최단거리 반환
    return visited


n, e = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    # 방향성이 없는 그래프
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, input().split())

# 최댓값
INF = 200000001

# 출발점이 다른 3가지 경우 (1, v1, v2)
start1 = dijkstra(1)
startV1 = dijkstra(v1)
startV2 = dijkstra(v2)
# 1, v1, v2, n 경우
case1 = start1[v1] + startV1[v2] + startV2[n]
# 1, v2, v1, n 경우
case2 = start1[v2] + startV2[v1] + startV1[n]
# 최단 거리
ans = min(case1, case2)
if ans < INF:
    print(ans)
else:
    print(-1)