[BOJ]9370번: 미확인 도착지

문제: https://www.acmicpc.net/problem/9370

---

아이디어가 필요한 최단경로 문제입니다.

 

시작점 S, 도착점 T 그리고 중간지점 노드를 G, H라 하겠습니다.

 

후보 T 노드를 가는 S->T 경로중에 G-H를 경유해서 가는 T노드가 몇 개 있는지 구하는 문제입니다.

 

일일이 지나온 경로를 저장해서 찾아도 되지만 그렇게 하면 시간초과가납니다.

 

해결방법은 S->T 경로를 다음과 같이 정의하는 것입니다.

S->G->H->T 또는 S->H->G->T 

 

다익스트라(start, end)의 리턴값을 출발 노드(start)부터 도착 노드(end)까지의 거리로 가정하겠습니다.

 

이 때 아래 조건을 만족하는 T를 전부 구하면 됩니다.

다익스트라(start: S, end: T) = 다익스트라(start: S, end: G) + 다익스트라(start: G, end: H) + 다익스트라(start: H, end: T)

 

시간복잡도는 O(100(T) * 100(t) * ElogV) 입니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ9370.java