[BOJ 1504] 특정한 최단 경로

문제 링크 : https://www.acmicpc.net/problem/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) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v₁과 v₂가 주어진다. (v₁ ≠ v₂, v₁ ≠ N, v₂ ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

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

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

이 문제는 1번 정점에서 출발하여 $N$번 정점에 도달하되, 중간에 반드시 거쳐야 하는 두 정점 $v_1$과 $v_2$를 포함하는 최단 경로를 찾는 문제이다. 그래프의 간선 가중치가 양수이므로 최단 경로 탐색을 위해 최단경로 :: 다익스트라 알고리즘을 활용한다.

반드시 거쳐야 하는 정점들을 포함하는 경로는 크게 두 가지 시나리오로 나뉜다:

1. $1 \rightarrow v_1 \rightarrow v_2 \rightarrow N$
2. $1 \rightarrow v_2 \rightarrow v_1 \rightarrow N$

최단경로 계산할 때, n1 -> v1 으로 갈 때 v2를 거쳐간다면 n1 -> v2 로 갈때에는 v1을 지날 수 없다. 즉 위에서 얘기한 2개의 시나리오를 모두 구하면 그 중에서 정답은 항상 존재함을 보장할 수 있다.

효율적인 계산을 위해 소스코드에서는 다음과 같은 방식을 사용하였다:

• 다익스트라 실행: $v_1$과 $v_2$를 각각 시작점으로 하여 두 번의 다익스트라 알고리즘을 수행한다. 이를 통해 각 정점에서 다른 모든 정점까지의 최단 거리를 구하며, 특히 $1$, $v_1$, $v_2$, $N$ 사이의 연결 관계를 파악한다.
• 최단 경로 비교:
  • 경로 1: $dist(1, v_1) + dist(v_1, v_2) + dist(v_2, N)$
  • 경로 2: $dist(1, v_2) + dist(v_2, v_1) + dist(v_1, N)$
  • 위 두 값 중 최솟값을 정답으로 선택한다. 무방향 그래프이므로 $dist(a, b) = dist(b, a)$ 성질이 성립함을 이용한다.
• 예외 처리: 만약 다익스트라 탐색 결과값이 설정해둔 무한대($INF$, $987\,654\,321$)보다 크거나 같다면, 해당 경로가 존재하지 않는 것이므로 $-1$을 출력한다.

정점의 개수 $N$이 최대 $800$개이고 간선 $E$가 $200\,000$개이므로, 다익스트라 알고리즘을 반복 호출하더라도 시간 제한 내에 충분히 통과할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 최단경로 :: 다익스트라 알고리즘