11724번: 연결 요소의 개수

문제 풀이 아이디어

완전탐색을 활용해서 해당 정점에 연결된 모든 요소를 탐색하면 됩니다. 그래프 완전탐색 알고리즘은 dfs와 bfs가 있습니다. 여기서는 dfs를 사용해서 구현해보겠습니다.

코드

// 연결 요소의 갯수

// dfs 구현
func dfs(_ node: Int) {
    check[node] = true
    
    for i in 1...N {
        if matrix[node][i] && !check[i] {
            dfs(i)
        }
    }
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
// (N + 1) * (N + 1) 크기의 인접 행렬
var matrix = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)
// 방문 체크용 배열
var check = Array(repeating: false, count: N + 1)
// 연결 요소의 갯수 count
var cnt = 0

for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    matrix[edge[0]][edge[1]] = true //👉 방향은 없으므로 두 군데 다 저장한다.
    matrix[edge[1]][edge[0]] = true
}

for i in 1...N {
    if !check[i] {
        cnt += 1
        dfs(i) //👉 여기서 dfs를 도는 동안 i와 연결된 요소들은 전부 check가 true가 된다.
    }
}

print(cnt)