백준 - 불우이웃돕기 (1414)

struct Edge {
    let start: Int
    let end: Int
    let value: Int
}

let N = Int(readLine()!)!
var queue = Heap<Edge>(sort: { $0.value < $1.value })
var sum = 0

// 에지 리스트 만들기
let a = Character("a").asciiValue!
let A = Character("A").asciiValue!

for i in 0..<N {
    let input = Array(readLine()!)
    for j in 0..<N {
        if input[j] == "0" { continue }
        let length: Int
        if input[j].isLowercase {
            length = Int(input[j].asciiValue! - a + 1)
        } else {
            length = Int(input[j].asciiValue! - A + 27)
        }
        sum += length
        if i != j { // 자기 자신을 향하는 에지는 리스트에 삽입하지 않음
            queue.insert(Edge(start: i, end: j, value: length))
        }
    }
}

// 최소 신장 트리 만들기
var parent = Array(0..<N)
var edgeCount = 0
var result = 0

while !queue.isEmpty() {
    let now = queue.remove()!
    if find(now.start) != find(now.end) {
        union(now.start, now.end)
        result += now.value
        edgeCount += 1
    }
}

print(edgeCount == N - 1 ? sum - result : -1)

// 유니온 파인드
func find(_ node: Int) -> Int {
    if parent[node] == node {
        return node
    }
    parent[node] = find(parent[node])
    return parent[node]
}

func union(_ a: Int, _ b: Int) {
    let aParent = find(a)
    let bParent = find(b)
    if aParent < bParent {
        parent[bParent] = aParent
    } else {
        parent[aParent] = bParent
    }
}

처음엔 어떻게 랜선 길이가 최댓값이 되게 기부를 한다는 건지 이해가 안 갔는데..😅

최소 길이의 랜선을 써서 다솜이의 집에 있는 컴퓨터 N개가 모두 연결되게 하고 남은 랜선들은 모두 기부한다는 의미였다.

즉, 전체 랜선 길이를 구한 다음 최소 신장 트리 알고리즘을 돌려서 트리의 가중치 값을 빼면 기부할 수 있는 랜선 길이의 최댓값을 구할 수 있다. 이때 모든 컴퓨터가 연결되지 않을 수 있다는 점을 주의해야 한다.

알파벳을 Int 값으로?

최소 신장 트리보다는 스위프트로 문자를 다루는 방식이 익숙하지 않아서 구글링의 힘을 빌려야 했던 문제였다. 특히 Character형과 관련된 속성들이 많다는 걸 알게 되었다. 평소에 관련 속성을 쓸 일이 거의 없어서 완전 까먹고 있었다 🥲

• 대소문자인지 확인할 때는 isLowercase , isUppercase
  • 원래는 ("a"..."z").contains() 같은 식으로 확인하려고 했는데 더 편한 속성이 존재했다..! 물론 이런 방법을 써도 결과는 잘 나오긴 한다.
• 문자의 아스키코드 값을 확인할 때는 asciiValue
  • 원래 각 값들을 String형으로 변환한 다음 UnicodeScalar(char)?.value 을 사용하려고 했는데 이 역시 Character형을 사용하면 훨씬 편하게 아스키코드 값을 얻을 수 있었다.