DFS/BFS_프로그래머스_네트워크

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

 

접근 방법

1. computers를 분석 -> connection =  n번 컴퓨터: n번 컴퓨터가 연결된 컴퓨터들
2. 재귀를 사용하여 방문한 컴퓨터의 수를 세어 리턴

은 문제 이해를 잘못하고 푼 것. 문제를 대충 읽는 버릇을 고쳐야한다...

 

문제는 연결된 컴퓨터의 그룹을 세는 것.

1. computers를 분석 -> connection =  n번 컴퓨터: n번 컴퓨터가 연결된 컴퓨터들
2. 재귀를 사용하여 0번 컴퓨터의 네트워크 탐색 -> return history 하여 연결된 컴퓨터들을 확인
3. connection의 key 중 history와 중복되는 key를 제외한 first를 다시 recursion 하여 key가 남지 않을 때까지 반복
4. 반복하며 반복 횟수를 count 하여 반환.

오답 코드: 문제를 잘 못 이해함.

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var connection: [Int:[Int]] = [:]
    
    computers.enumerated().forEach() { (index0, val) in
        val.enumerated().forEach() { (index1, con) in
            if connection[index0] == nil {
                connection[index0] = []
            }
            
            if index1 != index0 && con == 1 {
                connection[index0]!.append(index1)
            }
        }
    }
    print(connection)
    return searchNetwork(network: connection, next: 0)
}

func searchNetwork(network: [Int:[Int]], next: Int, history: Set<Int> = [], searched: Int = 0) -> Int {
    var newHistory = history
    var newSearched = searched
    
    var temp = [Int]()
    
    if newHistory.insert(next).inserted == true {
        newSearched += 1
    }
    print(newHistory)
    let canGo = network[next]!.filter() {
        !history.contains($0)
    }
    
    if canGo.isEmpty == true {
        return newSearched
    }
    
    canGo.forEach() {
        temp.append(searchNetwork(network: network, next: $0, history: newHistory, searched: newSearched))
    }
    
    return temp.max()!
}

 

오답코드 : 실패

forced unwrapping을 전부 제거하는 방향으로 수정해야겠다.

테스트 1 〉	통과 (0.27ms, 16.6MB)
테스트 2 〉	통과 (0.26ms, 16.5MB)
테스트 3 〉	실패 (signal: illegal instruction (core dumped))
테스트 4 〉	실패 (signal: illegal instruction (core dumped))
테스트 5 〉	통과 (0.14ms, 16.4MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (signal: illegal instruction (core dumped))
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (signal: illegal instruction (core dumped))
테스트 10 〉	실패 (signal: illegal instruction (core dumped))
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var connection: [Int:[Int]] = [:]
    var networkCount = 0
    
    computers.enumerated().forEach() { (index0, val) in
        val.enumerated().forEach() { (index1, con) in
            if connection[index0] == nil {
                connection[index0] = []
            }
            
            if index1 != index0 && con == 1 {
                connection[index0]!.append(index1)
            }
        }
    }
    
    while connection.isEmpty == false {
        networkCount += 1
        let result = searchNetwork(network: connection, next: connection.first!.key)
        result.forEach() {
            connection.removeValue(forKey:$0)
        }
    }
    
    return networkCount
}

func searchNetwork(network: [Int:[Int]], next: Int, history: Set<Int> = [], searched: Int = 0) -> [Int] {
    var newHistory = history
    var newSearched = searched
    
    var temp = [[Int]]()
    
    if newHistory.insert(next).inserted == true {
        newSearched += 1
    }
    
    let canGo = network[next]!.filter() {
        !history.contains($0)
    }
    
    if canGo.isEmpty == true {
        return Array(newHistory)
    }
    
    canGo.forEach() {
        temp.append(searchNetwork(network: network, next: $0, history: newHistory, searched: newSearched))
    }
    
    return temp.sorted(by: {
        $0.count > $1.count
    }).first!
}

오답 코드 : 로직 문제

현재 로직은 방문했던곳을 제거하는데, 이와 같은 경우 같은 네트워크에 연결되었을 지라도, 시작하는 컴퓨터에 따라서 네트워크 내의 컴퓨터를 전부 검출해내지 못하고 있다.

 

solution(4, [[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]) // 결과 1

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var connection: [Int:[Int]] = [:]
    var networkCount = 0
    
    computers.enumerated().forEach() { (index0, val) in
        val.enumerated().forEach() { (index1, con) in
            if connection[index0] == nil {
                connection[index0] = []
            }
            
            if index1 != index0 && con == 1 {
                connection[index0]!.append(index1)
            }
        }
    }
    print(connection)
    
    while connection.isEmpty == false {
        networkCount += 1
        guard let next = connection.first else { continue }
        guard let result = searchNetwork(network: connection, next: next.key) else {continue}
        print(result, "start : \(next)")
        result.forEach() {
            if connection[$0] != nil {
                connection.removeValue(forKey:$0)
            }
        }
    }
    
    return networkCount
}

func searchNetwork(network: [Int:[Int]], next: Int, history: Set<Int> = [], searched: Int = 0) -> [Int]? {
    var newHistory = history
    var newSearched = searched
    
    var temp = [[Int]]()
    
    if newHistory.insert(next).inserted == true {
        newSearched += 1
    }
    
    guard let target = network[next] else {
        return Array(newHistory)
    }
    
    let canGo = target.filter() {
        !newHistory.contains($0)
    }
    
    if canGo.isEmpty == true {
        return Array(newHistory)
    }
    
    canGo.forEach() {
        guard let result = searchNetwork(network: network, 
                                         next: $0, 
                                         history: newHistory, 
                                         searched: newSearched) else {
            return
        }
        temp.append(result)
    }
    
    return temp.sorted(by: {
        $0.count > $1.count
    }).first
}