https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
다익스트라 알고리즘을 통해 풀 수 있다.
풀이
출발 노선 지점에서 각 지점으로의 최소비용을 담을 dist:[Int]() 배열을 생성한다. 이후 입력되는 노선의 정보를 저장한 후 너비 우선 탐색을 통해 다음 노선까지의 비용이 더 저렴하다면 dist 원소 값을 경신한 후 값이 경신된 해당 지점을 큐에 담아 다음 탐색 경로에 추가해주면서 탐색을 수행하면 된다.
참고해야 할 점은 입력받은 노선 정보를 비용 기준 오름차순 정렬해주어야 한다는 점이다. 다익스트라 알고리즘의 조건인 최소비용부터 탐색한다는 조건을 생각하지 못해 정렬하지 않은 채로 제출했었는데 시간 초과가 일어났었다. 곰곰이 생각해보니 A -> B로 가는 노선이 여러 개일 경우 정렬을 하지 않은 채로 탐색을 수행한다면 큐에 중복된 경로를 추가하게 되어 불필요한 탐색을 수행하게 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [2096] 내려가기 (0) | 2022.11.29 |
|---|---|
| [3649] 로봇 프로젝트 (0) | 2022.11.26 |
| [1105] 팔 (0) | 2022.11.24 |
| [12015] 가장 긴 증가하는 부분 수열2 (0) | 2022.11.23 |
| [2166] 다각형의 면적 (0) | 2022.11.22 |