Hyun's_Devlog

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

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

풀이

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

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

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

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

정답 코드

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

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

정답 코드