DFS/BFS_Programmgers_네트워크 [swift]

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=swift#

프로그래머스

 

약 1시간 이내 즈음 걸렸다.

 

접근 방법

1. 모든 노드를 탐색해야 함
2. 첫 컴퓨터에서 탐색을 시작하였을 때, 연결된 노드만 탐색하면 미탐색 된 노드가 존재함.
3. 그러므로 모든 컴퓨터에 대하여 탐색을 수행하여야 하므로, computers: [[Int]]의 element를 전부 확인해야 함.
4. computer.Element를 탐색 할 때, 네트워크의 중간에서 시작 할 수 있으므로, 첫 노드에서 시작하여 반환된 결과값 전부를 Union하여 전체 네트워크를 알 수 있음.
   1. 각 재귀의 종료조건은, 매개변수로 제공받은 currentNetwork에 현재 탐색중인 컴퓨터의 index가 있을 경우 ( 중복 탐색 ), 노드의 끝에서는 결국 중복탐색이 발생하므로
   2. value가 0인경우 ( 연결되지 않음 )
5. Set의 형태로 얻어진 개별적인 네트워크를 Array<Int>.sorted로 변환한다. -> Array: Equtable하므로.
6. Set<[Int]>에 insert하여 중복을 제거한다.
7. Set<[Int]>.count를 정답으로 반환한다.

정답코드

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    func recursive(now: Int, currentNetwork: Set<Int>) -> Set<Int> {
        var partialReturn = currentNetwork
        for (index, value) in computers[now].enumerated() {
            guard value != 0 else { continue }
            if partialReturn.insert(index).inserted == false {
                continue
            }
            let nextNode = recursive(now: index, currentNetwork: partialReturn)
            partialReturn = partialReturn.union(nextNode)
        }
        
        return partialReturn
    }
    
    var sol: Set<[Int]> = []
    
    for selected in computers {
        var converted: [Int] = [] 
        selected.enumerated().forEach { (index, value) in
            if value == 1 { converted.append(index) }
        }
        
        let current = Set(converted)
        var partialResult: Set<Int> = []
        for next in converted {
            let output = recursive(now: next, currentNetwork: current)
            partialResult = partialResult.union(output)
        }
        let partialResultSortedArr = Array(partialResult).sorted()
        sol.insert(partialResultSortedArr)
    }
    
    return sol.count
}

 

성능

테스트 1 〉	통과 (0.28ms, 16.6MB)
테스트 2 〉	통과 (0.25ms, 16.2MB)
테스트 3 〉	통과 (4.78ms, 16.4MB)
테스트 4 〉	통과 (4.01ms, 16.3MB)
테스트 5 〉	통과 (0.21ms, 16.2MB)
테스트 6 〉	통과 (178.67ms, 16.6MB)
테스트 7 〉	통과 (0.43ms, 16.4MB)
테스트 8 〉	통과 (53.57ms, 16.5MB)
테스트 9 〉	통과 (32.24ms, 16.6MB)
테스트 10 〉	통과 (42.48ms, 16.4MB)
테스트 11 〉	통과 (1590.12ms, 16.8MB)
테스트 12 〉	통과 (922.14ms, 17.1MB)
테스트 13 〉	통과 (164.62ms, 16.6MB)

 

고수의 풀이를 봤는데 너무 간결해서 놀랐다.

놀라워서 적어놓는 고수의 풀이

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visit: [Bool] = Array(repeating: false, count: n)
    var answer: Int = 0

    func bfs(_ vertax: Int) {
        visit[vertax] = true
        for i in 0..<n {
            if computers[vertax][i] == 1 && visit[i] == false {
                bfs(i)
            }
        }
    }

    for i in 0..<n {
        if !visit[i] {
            answer += 1
            bfs(i)
        }
    }

    return answer
}