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

문제 소개

https://www.acmicpc.net/problem/11724

연결 요소의 갯수를 출력하는 문제이다.
 

문제 풀이

아래와 같이 그래프를 만들어서 dfs로 순회하는 식으로 문제를 풀었다.

import Foundation

let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, m) = (nm[0], nm[1])

var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
var visited = Array(repeating: false, count: n+1)
visited[0] = true

for _ in 0..<m {
    let uv = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (u, v) = (uv[0], uv[1])
    
    graph[u][v] = 1
    graph[v][u] = 1
}

var answer = 0

func dfs(_ node: Int) {
    visited[node] = true
    for i in 1...n {
        if graph[node][i] == 1 && !visited[i] {
            dfs(i)
        }
    }
}

for i in 1...n {
    if !visited[i] {
        answer += 1
        dfs(i)
    }
}

print(answer)