[Swift] BOJ 11724 연결 요소의 개수

 BOJ 11724 연결 요소의 개수

 

✅ 예전이면 이걸 어떻게 하지 싶었는데, 이제는 쉽게 풀어낼 수 있다.

BFS / DFS의 경우에는 tree형태로 이론을 배웠어서 그래프 형태면 늘상 포기하곤 했었는데, 그래프도 해결할 수 있었다니..! 신기해

 

근데 원래는 문제 풀다가 어려운거 아니면 포스팅 안하는데, 어느 순간부터인가 모든 문제를 포스팅 하고 있다.

나동빈 파이썬 책에서는 BFS가 DFS보다 빠르다라고 하였지만, 스위프트에서는 구현에 따라 BFS보다 DFS가 빠를 수 있다.

 

아래의 글은 내가 DFS / BFS를 구현한 알고리즘이다.

2022.04.02 - [코딩테스트] - [Swift] BOJ 1260 DFS와 BFS

 

나는 주로 BFS의 경우 removFirst를 이용하기 때문에, 배열의 write / read 작업이 들어가서 시간복잡도에서 손해를 본다.

그래서 백준에서 BFS로 분류된 문제였지만 이번 구현에서는 DFS를 사용한다. 물론 문제에 따라 다르게 적용하지만!! 

 

 

✅ 코드

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

struct b11724 {
    static func run() {
        let info = readLine()!.split(separator: " ").map{ Int("\($0)")! }
        var list = [Int: [Int]]()
        var keys: Set = Set<Int>()
        
        for _ in 0..<info[1] {
            let line = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let start = line[0]
            let end = line[1]
            
            if list[start] == nil {
                list[start] = [end]
                keys.insert(start)
            } else {
                list[start]?.append(end)
            }
            
            if list[end] == nil {
                list[end] = [start]
                keys.insert(end)
            } else {
                list[end]?.append(start)
            }
        }
        
        var count = info[0] - keys.count
        
        while !keys.isEmpty {
            count += 1
            // DFS
            var visitedQueue = [Int]()
            var needVisitStack = list[keys.first!]!
            
            while !needVisitStack.isEmpty {
                let node: Int = needVisitStack.removeLast()
                if visitedQueue.contains(node) { continue }
                keys.remove(node)
                
                visitedQueue.append(node)
                needVisitStack += list[node] ?? []
            }
            
            keys.subtract(visitedQueue)
        }
        

        print(count)
    }
}