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로 가는 노선이 여러 개일 경우 정렬을 하지 않은 채로 탐색을 수행한다면 큐에 중복된 경로를 추가하게 되어 불필요한 탐색을 수행하게 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| let n = Int(readLine()!)! | |
| let m = Int(readLine()!)! | |
| var dist = Array(repeating: Int.max, count: n) | |
| var map = Array(repeating: [(v:Int, cost:Int)](), count: n) | |
| for _ in 0..<m{ | |
| let line = readLine()!.split(separator: " ").map{Int($0)!} | |
| let u = line[0]-1 | |
| let v = line[1]-1 | |
| let cost = line[2] | |
| map[u].append((v,cost)) | |
| } | |
| for i in 0..<n{ | |
| map[i].sort(by: { $0.cost<$1.cost }) | |
| } | |
| let uv = readLine()!.split(separator: " ").map{Int($0)!-1} | |
| let u = uv[0] | |
| let v = uv[1] | |
| dist[u] = 0 | |
| var q = [(u)] | |
| var idx = 0 | |
| while idx<q.count{ | |
| let curr = q[idx] | |
| let cost = dist[curr] | |
| for info in map[curr]{ | |
| let next = info.v | |
| let fee = info.cost | |
| if dist[next] > cost+fee{ | |
| dist[next] = cost+fee | |
| q.append((next)) | |
| } | |
| } | |
| idx += 1 | |
| } | |
| print(dist[v]) |
'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 |