[23286] 허들 넘기

https://www.acmicpc.net/problem/23286

23286번: 허들 넘기

최단거리 탐색 알고리즘으로 접근한 문제다. 

---

풀이

특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.

 

정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.

 

따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.

 

즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.

---

정답 코드

---