Programmers) Lv3 섬 연결하기

출처: https://programmers.co.kr/learn/courses/30/lessons/42861

분류: Lv3 , Greedy

---

MST의 대표적인 문제입니다!!!

Prim 알고리즘으로 해결해봤는데요. 자세한 설명은 이론 설명 그 자체일 듯 합니당
다음글을 참고해주세용 :)

/**
 * 현재 노드에 연결되어 있는 노드만 확인할 것이기 때문에
 * 간단하게 목적지와 비용만 저장하는 Edge 를 정의합니다.
 */
struct Edge {
    var destination: Int
    var cost: Int
}

func updateDist(_ tree: [Edge], dist: inout [Int?]) -> [Edge] {
    for edge in tree {
        if let d = dist[edge.destination] {
            if d > edge.cost {
                dist[edge.destination] = edge.cost
            }
        } else {
            dist[edge.destination] = edge.cost
        }
    }
    
    return tree
}

func solution(_ n: Int, _ costs: [[Int]]) -> Int {
    
    // 최소 비용을 저장할 배열
    var dist = [Int?](repeating: nil, count: n)
    
    // 방문 체크 배열
    var visit = [Bool](repeating: false, count: n)
    
    // 방문한 노드의 개수 ( 방문 체크 배열에서 확인해도 되지만.. 그냥 간단하게 변수를 하나 만들었습니다. )
    var visitCount = 0
    
    // 현재 방문 노드를 저장합니다. 0에서 시작합니다.
    var now = 0
    
    // 최소비용을 저장한다.
    var minimumCost = 0
    
    /**
     * 배열의 인덱스가 해당 노드가 되고 연결된
     * 연결된 선을 저장합니다.
     */
    var tree = [[Edge]](repeating: [], count: n)
    
    /**
     * Setup Tree
     * 선의 양 끝을 둘다 저장해줘야 합니다.
     */
    for cost in costs {
        tree[cost[0]].append(Edge(destination: cost[1], cost: cost[2]))
        tree[cost[1]].append(Edge(destination: cost[0], cost: cost[2]))
    }
    
    visit[now] = true
    visitCount += 1
    
    // 탐색
    while visitCount < n {
        let tree = updateDist(tree[now], dist: &dist)
        
        // 최소값 구하기
        var minCost: Int? = nil
        for i in 0..<n {
            guard !visit[i], let d = dist[i] else {continue}
            
            if let min = minCost {
                if min > d {
                    minCost = d
                    now = i
                }
            } else {
                minCost = d
                now = i
            }
        }
        
        visit[now] = true
        visitCount += 1
        minimumCost += minCost!
    }
    
    
    return minimumCost
}