안녕하세요 !
https://programmers.co.kr/learn/courses/30/lessons/42861
풀이
최소 신장 트리 중 프림 알고리즘을 이용하여 풀었습니다.
시작 노드를 0으로 가정하고 모든 섬을 통행하는 가장 적은 비용을 구합니다. (시작점을 어디로 하든 상관없습니다.)
import Foundation
func prim(_ graph: [Int: [(Int, Int)]], _ n: Int) -> Int {
var check = Array(repeating: false, count: n)
var pq: [(cost: Int, index: Int)] = []
var minCost = 0
// 0번 섬에서 시작한다고 가정
check[0] = true
// 0번섬과 인접한 섬 우선순위큐에 넣어줌
for (adjacent, cost) in graph[0]! {
pq.append((cost, adjacent))
}
while !pq.isEmpty {
// 비용 기준으로 내림차순 정렬
pq.sort { $0.cost > $1.cost }
let minCostPop = pq.removeLast()
let currentCost = minCostPop.cost
let currentNode = minCostPop.index
// 가지 않은 섬만 추가
if !check[currentNode] {
check[currentNode] = true
minCost += currentCost
for (adjacent, cost) in graph[currentNode]! {
if !check[adjacent] {
pq.append((cost, adjacent))
}
}
}
}
return minCost
}
func solution(_ n:Int, _ costs:[[Int]]) -> Int {
var answer = 0
var graph: [Int: [(Int, Int)]] = [:]
// 양방향 graph 만들기
for road in costs {
let a = road[0]
let b = road[1]
let cost = road[2]
if let _ = graph[a] {
graph[a]!.append((b, cost))
} else {
graph[a] = [(b, cost)]
}
if let _ = graph[b] {
graph[b]!.append((a, cost))
} else {
graph[b] = [(a, cost)]
}
}
return prim(graph, n)
}