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로 가는 노선이 여러 개일 경우 정렬을 하지 않은 채로 탐색을 수행한다면 큐에 중복된 경로를 추가하게 되어 불필요한 탐색을 수행하게 된다.

 

정답 코드

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])
view raw 1916.swift hosted with ❤ by GitHub

 

'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

+ Recent posts