BOJ-11724 연결 요소의 개수 Swift

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

내가 푼 풀이

- 연결요소는 점이 주어졌을 때, 연결된 점의 무리들의 총개수를 말한다.

- 한 점이 어떤 점도 연결되어있지 않아도, 연결요소에 포함된다.

- 해당 점과 연결리스트를 작성하고, 순서는 상관없으므로 BFS , DFS 아무거나 사용해서 연결된 점들을 모두 탐색하면 연결요소 + 1 이 되는 형식으로 짰다.

 

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var graph = [Int: [Int]]()
var start = [Int]()
var result = 0
var visitedQueue = [Int]()
var needVisitQueue = [Int]()

// 연결리스트 작성
for i in 0..<input[1] {
    var inp = readLine()!.split(separator: " ").map{ Int($0)! }
    
    if graph[inp[0]] == nil {
        graph[inp[0]] = [inp[1]]
    } else {
        graph[inp[0]]!.append(inp[1])
    }
    if graph[inp[1]] == nil {
        graph[inp[1]] = [inp[0]]
    } else {
        graph[inp[1]]!.append(inp[0])
    }
    
    if !start.contains(inp[0]) {
        start.append(inp[0])
    }
    if !start.contains(inp[1]) {
        start.append(inp[1])
    }
}

// 연결되어 있지 않은 점도 본인의 점으로 연결
for i in 1...input[0] {
    if graph[i] == nil {
        graph[i] = [i]
        start.append(i)
    }
    
}

// 주어진 점 모두 탐색할때까지 DFS
while visitedQueue.count != start.count {
    var node = 0
    for i in 0..<start.count {
        if !visitedQueue.contains(start[i]) {
            node = start[i]
            break
        }
    }
    needVisitQueue.append(node)
    result += 1
    
    while !needVisitQueue.isEmpty {
        var n = needVisitQueue.removeLast()
        if visitedQueue.contains(n) { continue }
        visitedQueue.append(n)
        
        needVisitQueue += graph[n]!
    }
}

print(result)