그래프_백준_11724 swift

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

11724번: 연결 요소의 개수

 

문제접근

1. 1...N의 정점, 첫번째 (1) 부터 반복문 수행
2. 중복 여부 검사 후( visited에 있는가? 여부), 간선 연결됨 +1 (connected+=1)
3. dfs하여 1과 연결된 모든 정점 탐색 및 visited에 insert
4. 1번의 반복문을 이어서 시행 -> visited에 포함된 요소들은 건너 뜀 continue

testcase

let firstInput = "6 5" // answer :2
let inputList = ["1 2",
"2 5",
"5 1",
"3 4",
"4 6"]

let secondInput = "6 8" //1
let inputList2 = ["1 2",
"2 5",
"5 1",
"3 4",
"4 6",
"5 4",
"2 4",
"2 3"]

let thirdInput = "6 2" //4
let inputList3 =
["3 4",
"4 2"]

정답

메모리	시간
104280KB	2216ms

class Baek11724 {
    
    struct Connection {
        let left: Int
        let right: Int
    }
    
    var connected = 0
    var connections = [Connection]()
    var visited: Set<Int> = []
    
    func start(_ N: Int, _ input: [String]) {
        var wholeNums = Set<Int>()
        
        
        for i in 1...N {
            wholeNums.insert(i)
        }
        
        for str in input {
            let intArr = str.components(separatedBy: .whitespaces).map({Int($0)!})
            connections.append(Connection.init(left: intArr[0], right: intArr[1]))
        }
        
        for num in wholeNums.sorted() {
            if !visited.insert(num).inserted {
                continue
            }
            print(visited)
            connected += 1
            dfs(num)
        }
        
        
        
        wholeNums.subtract(visited)
        connected += wholeNums.count
        print(connected, wholeNums.count)
    }
    
    func dfs(_ num: Int) {
        for conn in connections {
            if conn.left == num && !visited.contains(conn.right) {
                visited.insert(conn.right)
                dfs(conn.right)
            }
            if conn.right == num && !visited.contains(conn.left) {
                visited.insert(conn.left)
                dfs(conn.left)
            }
        }
    }
}