[BOJ][🟡4][백준#01504] 특정한 최단 경로

문제 출처

BAEKJOON Online Judge #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을 출력한다.

예제

입력

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

출력

7

My Sol

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from math import inf

def dijk(S, E):
    global G

    visit = [0]*(V+1)
    D = [inf]*(V+1)
    D[S] = 0
    Q = [(D[S], S)]
    while Q:
        val, u = heappop(Q)
        if visit[u]: continue
        visit[u] = 1

        for v, w in G[u]:
            if not visit[v] and D[v] > D[u] + w:
                D[v] = D[u] + w
                heappush(Q, (D[v], v))
    return -1 if D[E] == inf else D[E]


def main(S, A, B, T):
    R1 = dijk(S, A)
    if R1==-1: return -1
    R2 = dijk(A, B)
    if R2==-1: return -1
    R3 = dijk(B, T)
    if R3==-1: return -1
    return R1+R2+R3


V, E = map(int, input().split())
G = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))

C1, C2 = map(int, input().split())
ret1 = main(1, C1, C2, V)
ret2 = main(1, C2, C1, V)
ret3 = {ret1, ret2} - {-1}
print(min(ret3) if ret3 else -1)

다익스트라 알고리즘을 변형한 방식이다. 반드시 지나야하는 두 정점을 C1과 C2로 저장하고, 총 3번의 다익스트라 알고리즘을 적용하여 1번 정점부터 V번 정점까지 도달하는 최단 경로를 확인한다. 이때 C2를 먼저 방문할 것인지, C1을 먼저 방문할 것인지를 완전 탐색을 통해 확인하여 출력하면 된다.

이때 다익스트라 함수를 만들어 일정 구간의 최단 경로의 값을 구했는데, 이 값이 -1을 반환한다면 두 정점이 이어지지 않은 것이다. 그런데 두 가지 경우 모두 C1과 C2는 지나므로, 이를 먼저 확인하여 백트래킹처럼 경우를 잘라줬어도 됐겠다. 불필요한 경로 계산을 한 번 더 한 것 같다.

결과

맞았습니다!!