[Swift] 프로그래머스(Lv3) - 섬 연결하기

안녕하세요 !

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)
}