문제 소개
보자마자 최소 신장 트리 (MST, Minimum Spanning Tree) 문제구나! 왜냐하면 최소경로로 마을을 잇는 방법을 구하는 것이기 때문이다.
문제 풀이
Union find 알고리즘을 사용하여 최소 신장 트리를 만들었다. 그리고 마을을 두개로 나눈다고 했으니 최소 신장 트리에서 가장 긴 경로를 끊었다. 아래의 포스팅에 Union-Find 알고리즘을 활용하였다.
import Foundation
let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var inputs = [[Int]]()
for _ in 0..<m {
let abc = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b, c) = (abc[0], abc[1], abc[2])
inputs.append([a, b, c])
}
var parents = Array(0...n)
func find(_ n: Int) -> Int {
if parents[n] != n {
parents[n] = find(parents[n])
}
return parents[n]
}
func union(_ a: Int, _ b: Int) {
let a = find(a)
let b = find(b)
if a < b {
parents[b] = a
} else {
parents[a] = b
}
}
inputs.sort { $0[2] < $1[2] }
var answer = 0
var maxValue = 0
for input in inputs {
if find(input[0]) != find(input[1]) {
union(input[0], input[1])
maxValue = max(maxValue, input[2])
answer += input[2]
}
}
print(answer - maxValue)
'→ Problems' 카테고리의 다른 글
[Algorithm] 백준 - 1806번 부분합 (Swift) (0) | 2024.06.21 |
---|---|
[Algorithm] 백준 - 1005번 ACM Craft (Swift) (0) | 2024.06.20 |
[Algorithm] 백준 - 1197번 최소 스패닝 트리 (Swift) (1) | 2024.06.18 |
[Algorithm] 백준 - 27172번 수 나누기 게임 (Swift) (1) | 2024.06.18 |
[Algorithm] 백준 - 2467번 용액 (Swift) (0) | 2024.06.17 |