코딩테스트 연습 - 네트워크

문제 풀이 아이디어

전형적인 dfs 문제입니다. 모든 node를 탐색하면서 아직 방문하지 않은 node가 있으면 dfs를 통해 연결된 node들을 전부 방문 처리해주면 됩니다. 입력이 행렬 형태로 주어집니다.

코드

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    // 네트워크 개수를 기록할 변수와 방문 체크 배열
    var result = 0
    var visited = Array(repeating: false, count: n)
    
    // dfs 구현
    func dfs(_ now: Int) {
        // 모든 node에 대해서 연결된 node && 아직 미방문 node가 있으면 dfs
        for i in 0..<computers.count {
            if computers[now][i] == 1 && !visited[i] {
                visited[i] = true //👉 방문한 곳에는 방문체크
                dfs(i)
            }
        }
    }
    
    // 모든 미방문 node에 대해 dfs 실시
    for i in 0..<computers.count {
        if !visited[i] {
            dfs(i)
            result += 1
        }
    }
    
    return result
}