[Swift] 백준 11724: 연결 요소의 개수

 문제 사이트 

11724번: 연결 요소의 개수

 

---

 알고리즘 

1. n, m을 입력받는다.
2. graph를 초기화한다. (빈 배열, 길이 = node 개수 + 1)
3. 방문확인 여부를 저장하는 배열을 만든다. (node 개수 + 1)
4. 간선을 입력받아 graph에 저장한다. (양방향으로 저장할 수 있도록)
5. dfs를 실행한다.
6. main에서 실행된 dfs의 수 = 연결 요소의 개수

---

 나의 코드 

let datas = readLine()!.split(separator: " ").map{ Int($0)! }
var graph = [[Int]](repeating: [], count: datas[0] + 1)
var visited = [Bool](repeating: false, count: datas[0] + 1)
var result = 0
for _ in 0..<datas[1]{
    let edges = readLine()!.split(separator: " ").map{ Int($0)! }
    graph[edges[0]].append(edges[1])
    graph[edges[1]].append(edges[0])
}
for node in 1...datas[0]{
    if !visited[node]{
        result += dfs(v: node)
    }
}
print(result)

func dfs(v: Int) -> Int{
    visited[v].toggle()
    for node in graph[v]{
        if !visited[node]{
            dfs(v: node) // 여기서 호출된건 신경쓰지 않기!
        }
    }
    return 1
}

 

---

 Key Point 

📍 main에서 호출된 dfs만 신경쓰는 것이 가장 중요

📍 dfs의 알고리즘 구현에 능숙해지자!