[Algorithm] 백준 - 1647번 도시 분할 계획 (Swift)

문제 소개

보자마자 최소 신장 트리 (MST, Minimum Spanning Tree) 문제구나! 왜냐하면 최소경로로 마을을 잇는 방법을 구하는 것이기 때문이다.
 

 

문제 풀이

Union find 알고리즘을 사용하여 최소 신장 트리를 만들었다. 그리고 마을을 두개로 나눈다고 했으니 최소 신장 트리에서 가장 긴 경로를 끊었다. 아래의 포스팅에 Union-Find 알고리즘을 활용하였다.

[Algorithm] Union-Find 알고리즘 (Swift)

 

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)