[백준 스위프트] 11724번 연결 요소의 개수

아이디어

핵심 키워드를 모르면 못 푼다. 방향 없는 그래프와 연결 요소가 무엇인지 알아야 한다. 

먼저 다른 문제와 같이 그래프를 만들고 dfs를 이용해서 풀었다. check 혹은 visited를 만들고 for문에서 순회하면서 방문하지 않았다면 연결 요소 수치인 result를 증가시키고 방문 처리를 한다. 다음으로 dfs 함수를 돌리는데 여기서는 해당 행에서 방문하지 않은곳을 찾는다. 마지막으로 자기 자신을 재귀로 호출하면 끝에서 타고 올라가며? 처리를 한다. 

해답

let input = readLine()!.split(separator: " ").map { Int(String($0))!}
let N = input[0]
let M = input[1]
var graph = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)
var check = Array(repeating: false, count: N + 1)
var result = 0
for _ in 0 ..< M {
    let line = readLine()!.split(separator: " ").map{Int(String($0))! }
    graph[line[0]][line[1]] = true
    graph[line[1]][line[0]] = true
}
func dfs(_ i: Int){
    for j in 1 ... N {
        if graph[i][j] && !check[j] {
            check[j] = true
            dfs(j)
        }
    }
}
for i in 1 ... N {
    if !check[i] {
        result += 1
        check[i] = true
        dfs(i)
    }
}
print(result)