[고득점 Kit (DFS/BFS)] 네트워크 (swift)

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

 

 

풀이

---

 

네트워크 확인 여부를 위한 Bool형 배열을 하나 만들어준다.

만약 컴퓨터 번호에 해당하는 Bool 값이 true이면 이미 하나의 네트워크에 포함된 컴퓨터임을 의미한다.

for문으로 모든 컴퓨터 번호를 체크해서 만약 해당 컴퓨터 번호가 아직 어떤 네트워크에도 속하지 않았다면 dfs 함수를 호출해서 모든 연결되어있는 컴퓨터 번호를 체크하는 과정을 거친다. dfs가 호출될때마다 네트워크 개수를 하나 증가시켜주고 최종적으로 해당 개수를 return 해주면 된다.

 

코드

---

import Foundation

var visited: [Bool] = [] // 네트워크 확인 여부 배열
var coms: [[Int]] = [[]]
var N: Int = 0
var res: Int = 0

func dfs(idx: Int) {
    for i in 0..<N {
        if visited[i] || i == idx {
            continue
        }
        
        // 연결되어 있으면 다시 한 번 dfs를 호출해서 체크해준다.
        if coms[idx][i] == 1{
            visited[i] = true
            dfs(idx: i)
        }
    }
}

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    visited = [Bool](repeating: false, count: n)
    coms = computers
    N = n
    
    // 각 컴퓨터를 돌면서 이미 네트워크 확인한 컴퓨터(visited[컴퓨터]가 true인 경우)일 때는 dfs를 안타도록 continue 해줌
    for i in 0..<n {
        if visited[i] {
            continue
        }
        
        // dfs가 호출되면 네트워크 개수를 1 증가시켜주고 네트워크 확인에 체크
        res += 1
        visited[i] = true
        dfs(idx: i)
    }
    
    return res
}