[Swift][DFS] 백준 11724번 (연결 요소의 개수)

요구능력 : DFS와 인접리스트에 대한 이해

 

코드설명 : 

 

평범한 DFS문제처럼 인접리스트를 구해준다.

문제에서 따로 함수를 빠져나갈 조건이 나오지 않았으므로 사실 depth도 필요는 없다. 그냥적은거다.

조건이 없으니 방문처리만하고 나가는 처리는 할필요가 없다.

 

여기서 핵심은 인접리스트를 다 돌면서 이미 방문한 노드들은 돌지않고

돌게되는 인접리스트는 카운트를 해주는 것이다.

이미 방문한 노드들은 한개의 묶음의 노드이기 때문이다. (하나의 연결요소이기 때문이다.)

DFS는 같은 묶음에 있는 노드는 다 돌게 되어있다.

그러니 방문하지 않은 노드는 다른 연결요소라는 뜻이다.

 

후기 : DFS문제는 아직 어렵다 .. 적응이 좀 더 필요하다..

 

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = arr[0] //정점의 개수
let m = arr[1] //간선의 개수
var depth = 0
var list: [[Int]] = Array(repeating: [], count: n + 1)
var visited: [Bool] = Array(repeating: false, count: n + 1)
var count = 0

for _ in 1...m {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    list[line[0]].append(line[1])
    list[line[1]].append(line[0])
}



func dfs(_ now: Int ,_ depth: Int) {
    visited[now] = true
    for i in 0..<list[now].count{
        let next = list[now][i]
        if !visited[next]{
            dfs(next, depth + 1)
        }
    }
}


for i in 1...n{ //핵심
    if !visited[i]{
        count += 1
        dfs(i, depth)
    }
}

print(count)