[Swift] BOJ 1197 네트워크 연결 (🎉 400번째 포스팅이다 ㅎㅎ)

BOJ 1197 네트워크 연결

 

🎉 시작하기에 앞서

🎉 400번째 포스팅이다 ㅎㅎ

400번째 글

 

꾸준히 공부한 것들을 기록하고 있는데, 다음 100개의 포스팅은 SwiftUI로 꽉꽉 채워보자!

 

✅ 최소 스패닝 트리의 기본적인 유형이다.

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)

    }
}