백준 1504번: 특정한 최단 경로 (Python)

접근

바로 전 문제인 최단 경로 문제와 유사하지만 특정 경로를 거쳐야 한다는 점과 방향성이 없다는 점을 고려하여 풀어주면 된다.

최단 경로 문제 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python)

백준 1753번: 최단경로 (Python)

기본적으로 최단경로를 구하는 다익스트라 알고리즘을 이용하여 풀었다. ( 다익스트라 알고리즘 ) 방향성이 없는 점은 처음에 그래프를 추가할 때, 서로를 목적지로 하는 두개의 경로를 추가해주면 된다. 그리고 특정 정점을 거쳐야 하는 문제는 다음과 같이 해결하였다.

거쳐야 하는 두개의 점을 f, g라고 할 때,

1. 1에서 f 가는 최단거리 + g에서 n 가는 최단 거리
2. 1에서 g 가는 최단거리 + f에서 n 가는 최단 거리

위 두가지 중 작은 값에 f에서 g 가는 최단거리를 더해주었다.

코드

import sys
import heapq

v, e = map(int, sys.stdin.readline().split())
lines = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    lines[a].append([c, b])
    lines[b].append([c, a])
f, g = map(int, sys.stdin.readline().split())


def Dijkstara(start, end):
    visited = [float('inf') for _ in range(v + 1)]
    visited[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        weight, now = heapq.heappop(heap)
        if visited[now] < weight:
            continue
        for w, n in lines[now]:
            nw = w + weight
            if nw < visited[n] and nw < visited[end]:
                visited[n] = nw
                heapq.heappush(heap, (nw, n))
    return visited[end]


route11 = Dijkstara(1, f)
route12 = Dijkstara(g, v)
route21 = Dijkstara(1, g)
route22 = Dijkstara(f, v)
ans = min(route11 + route12, route21 + route22) + Dijkstara(f, g)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!