[Swift] BOJ 1197 네트워크 연결

BOJ 1197 네트워크 연결

 

접근 방식

 

최소 스패닝 트리 기본형. 크루스칼로 풀되 사이클 판정은 find-union으로 처리함. 간선을 비용 오름차순으로 정렬하고, 두 끝점의 루트가 다를 때만 비용을 더함.

 

알고리즘 자체는 익숙한데 구현에서 자잘한 실수가 반복돼서 그 부분을 정리함.

 

시행착오

 

 

최소 스패닝 트리에서의 내 실수들

 

1. union 함수에서 num1, num2도 find 함수를 통해 구해야 함. (자꾸 parent[i]로 세팅하는 실수를 범함)
2. parent의 개수를 지정할 때는 노드의 개수(정점의 수)만큼 지정해야 함. (실수로 간선의 개수로 설정하기도 함)
3. 간선의 리스트를 세팅할 때는 정점의 개수가 아닌 간선의 개수로 해야 함. (이 문제에서는 이것 때문에 한참 헤맸음)
4. 비용을 기준으로 오름차순으로 정렬함. (정렬도 깜빡한 적 있음)
5. 두 부분으로 나눌 때는 last 값을 기록해서 빼줌.
6. 그래프를 입력받으면서 세팅해야 시간 면에서 유리함. (백준에서 스위프트 언어 사용하면 시간 초과가 남)
7. 튜플을 주로 쓰는데, 그냥 배열을 쓰는 게 여기서는 나음. (이것도 백준에서 시간 초과 문제)
8. find 함수에서 parent[i] = find(i)로 넣는 실수를 하는데 find(parent[i])로 넣어야 함.

 

코드

 

// https://www.acmicpc.net/problem/1922
import Foundation

struct b1922 {
    static func run() {
        let v = Int(readLine()!)!

        let e = Int(readLine()!)!
        var graph: [[Int]] = []

        var parent = Array(0...v)

        
        func find(i: Int) -> Int {
            if parent[i] == i {
                return i
            } else {
                parent[i] = find(i: parent[i])
                return parent[i]
            }
        }

        func union(a: Int, b: Int) {
            let num1 = find(i: a)
            let num2 = find(i: b)

            // 무조건 병합해야해.
            if num1 < num2 {
                parent[num2] = num1
            } else {
                parent[num1] = num2
            }
        }
        
        // 2차원 배열로 세팅함.
        for _ in 0..<e {
            graph.append(readLine()!.split(separator: " ").map { Int($0)! })
        }

        graph.sort { $0[2] < $1[2] }
        var result = 0
        for element in graph {
            let a = element[0]
            let b = element[1]
            let cost = element[2]

            if find(i: a) != find(i: b) {
                // 달라야 사이클이 아니다.
                result += cost
//                print(result)
                union(a: a, b: b)
            }
        }
        print(result)

    }
}