파티 - 1238
다익스트라는 어떤 한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘이다.
이 문제에서는
A. X에서 다른 모든 점들까지의 모든 최단거리와
B. 다른 모든 점에서 X까지의 최단거리를 구해야한다.
( 양방향 그래프가 아니므로 가는길과 오는길의 비용은 다를 수 있다 )
한번의 다익스트라를 통해 A번을 해결할 수 있다.
하지만 B번같은 경우는 다른 모든점에서 총 N-1번의 다익스트라를 수행해야한다.
시간복잡도를 계산해보면 한번의 다익스트라는 O(MlogN)이고 총 N번 수행하므로
O(NMlogN)의 시간복잡도를 가진다.
N, M을 대입해서 계산해보면 NMlogN ≒ 10001000010- = 1억- 이다.
즉 1억의 계산이 1초정도 걸리므로 문제의 제한시간을 만족하기는 하나 약간은 애매하기도 하다.
여기서 역방향 그래프 라는 아이디어를 챙겨가자.
역방향 그래프란 기존에 존재하던 그래프의 간선방향을 모두 반대로 바꾼 그래프이다.
A에서 B로 이동하는 최단거리가 X인 그래프가 있다고 해보자.
이 그래프의 간선방향을 모두 반대로 바꾸면 간선의 방향만 바뀌고 간선들의 연결 지점들은 모두 동일하므로
B에서 A로 가는 최단거리는 X임이 자명하다.
이 논리를 문제 상황에 맞춰보면 기존 그래프의 다른 모든 지점에서 X까지의 최단거리는
역방향 그래프에서 X에서 다른 모든지점까지의 최단거리와 같다.
즉, 역방향 그래프에서 X를 기준으로 한번의 다익스트라를 통해 다른 모든 지점까지의 최단거리를 구할 수 있다.
X에 가는 최단거리 한번과 X에서 오는 최단거리를 단 두 번의 다익스트라를 통해 구할 수 있다.
시간복잡도는 O(2MlogN) = O(MlogN) = 10000*10- = 100000- 이므로
속도가 약 100배정도 더 빨라졌다.