[swift] 백준 - 11724번: 연결 요소의 개수

11724번: 연결 요소의 개수

---

성공 풀이 (BFS)

let NM = readLine()!.split(separator: " ").map { Int($0)! }
let N = NM[0], M = NM[1]
var arr = Array(repeating: [Int](), count: N+1)
var visited = [Bool](repeating: false, count: N+1)
var count = 0
for _ in 0..<M {
    let i = readLine()!.split(separator: " ").map { Int($0)! }
    arr[i[0]].append(i[1])
    arr[i[1]].append(i[0])
}
for i in 1...N {
    var queue = [Int]()
    if visited[i] { continue }
    queue.append(i)
    while !queue.isEmpty {
        let n = queue.removeFirst()
        visited[n] = true
        for j in arr[n] {
            if !visited[j] && !queue.contains(j) {
                queue.append(j)
            }
        }
    }
    count += 1
}
print(count)

풀이 키워드

BFS
기본적인  그래프 탐색 문제다.
queue를 사용해 넓이 우선 탐색을 했다.
따로 함수를 사용하지 않아 난잡해 보인다.

---

성공 풀이 (DFS)

let NM = readLine()!.split(separator: " ").map { Int($0)! }
let N = NM[0], M = NM[1]
var arr = Array(repeating: [Int](), count: N+1)
var visited = [Bool](repeating: false, count: N+1)
var count = 0
for _ in 0..<M {
    let i = readLine()!.split(separator: " ").map { Int($0)! }
    arr[i[0]].append(i[1])
    arr[i[1]].append(i[0])
}
func dfs(_ n:Int) {
    visited[n] = true
    for i in arr[n] {
        if !visited[i] {
            dfs(i)
        }
    }
}
for i in 1...N {
    if !visited[i] {
        dfs(i)
        count+=1
    }
}
print(count)

풀이 키워드

DFS

---