https://www.acmicpc.net/problem/17396
17396번: 백도어
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는
www.acmicpc.net
최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.
풀이
접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.
swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.
글 읽기 - 다익스트라 시간초과 질문드립니다
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다.
우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.
즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸 현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.
따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [23286] 허들 넘기 (0) | 2024.01.18 |
|---|---|
| [5582] 공통 부분 문자열 (0) | 2024.01.12 |
| [23040] 누텔라 트리 (Easy) (0) | 2023.11.10 |
| [20530] 양분 (0) | 2023.11.04 |
| [15559] 내 선물을 받아줘 (0) | 2023.10.31 |