[Algorithm] 네트워크

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

💬 Idea

네트워크를 표현하는 연결 리스트 그래프를 먼저 만든 후, 0부터 시작하여 연결된 모든 노드를 탐색한다.

1. 이렇게 한 네트워크망이 생성되면 +1을 한다.
2. 네트워크망 생성 후 아직 탐색되지 않은 노드가 남아있다면, 해당 노드를 start로 하여 또 다른 네트워크망이 있는지 탐색한다.
3. 네트워크가 남아있지 않을때까지 1-2를 반복한다.

💬 풀이

func solution(n:Int, computers:[[Int]]) -> Int {
    var networkDict: [Int: [Int]] = [:]
    
    for (i, ci) in computers.enumerated() {
        if networkDict[i] == nil {
            networkDict[i] = []
        }
        
        for (j, _) in ci.enumerated() {
            if computers[i][j] == 1 {
                networkDict[i]?.append(j)
            }
        }
    }
    return dfsToFindNetwork(networkDict, 0)
}

func dfsToFindNetwork(_ arr: [Int: [Int]], _ start: Int) -> Int {
    var arr = arr
    var networkCount = 0
    var needVisitStack: [Int] = [start]
    var visitedQueue: [Int] = []
    
    while !needVisitStack.isEmpty {
        let node = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitStack += arr[node] ?? []
        
        if ((arr[node]?.isEmpty) != nil) {
            arr.removeValue(forKey: node)
        }
    }
    networkCount += 1
    
    if arr.count > 0 {
        networkCount += dfsToFindNetwork(arr, arr.first!.key)
    }
    
    return networkCount
}