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

BOJ 11724 연결 요소의 개수

 

접근 방식

 

연결 요소의 개수는 간선으로 이어진 노드 덩어리가 몇 개인지 세는 문제.

 

인접 리스트로 그래프를 만들고 간선에 등장한 노드를 keys 집합에 모음. keys에서 하나를 꺼내 DFS로 한 덩어리를 전부 훑은 뒤 방문한 노드를 keys에서 빼는 과정을 반복하면, 반복 횟수가 덩어리 수가 됨. 간선에 한 번도 등장하지 않은 고립 노드는 info[0] - keys.count로 미리 더해둠.

 

트리 형태로만 익혀서 그래프가 나오면 늘 막혔는데, 인접 리스트로 양방향 연결을 담으면 그래프도 같은 방식으로 풀림.

 

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

 

아래 글에 내가 구현한 DFS / BFS 알고리즘이 있음.

 

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

 

나는 주로 BFS의 경우 removeFirst를 이용하기 때문에 배열의 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)
    }
}