백준 1922 네트워크 연결

출처: www.acmicpc.net/problem/1922

분류: kruskal

---

접근방식

최소 비용으로 모든 간선을 연결할 수 있는 경우를 찾는 크루스칼 알고리즘을 연습해볼 수 있는 문제였습니다.

별다른 트릭은 없어서 크루스칼 알고리즘을 이해하고 있다면 쉽게 해결할 수 있습니다.

간선을 정렬하고 사이클이 생기지 않도록 합쳐주면서 간선의 개수를 노드-1개까지 선택해주면 됩니다.

사이클은 union-find 알고리즘으로 확인할 수 있습니다.

 

해결방법

let n = Int(readLine()!)!
var graph = [[Int]](repeating: [Int](repeating: 10001, count: n+1), count: n+1)
var unionTable = [Int]()

for i in 0...n {
    unionTable.append(i)
}

typealias Edge = (a: Int, b: Int, cost: Int)
var edges = [Edge]()

for _ in 0..<Int(readLine()!)! {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    edges.append(Edge((edge[0], edge[1], edge[2])))
}

func find(of idx: Int) -> Int {
    guard unionTable[idx] != idx else { return idx }
    unionTable[idx] = find(of: unionTable[idx])
    return unionTable[idx]
}

func union(_ a: Int, _ b: Int) {
    let aParents = find(of: a)
    let bParents = find(of: b)
    
    if aParents < bParents {
        unionTable[bParents] = aParents
    } else {
        unionTable[aParents] = bParents
    }
}

edges.sort(by: { $0.cost < $1.cost })
var connectEdges = 0
var connectCost = 0
for (a, b, cost) in edges {
    guard connectEdges < n else { break }
    let aParents = find(of: a)
    let bParents = find(of: b)
    
    if aParents == bParents {
        continue
    } else {
        union(a, b)
        connectEdges += 1
        connectCost += cost
    }
}

print(connectCost)

 

 

배운점