[프로그래머스] 네트워크 (Swift)

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

프로그래머스

 

 

• comupters는 나를 포함하여 연결된 컴퓨터정보임
• 나를 제외한 연결된 노드들을 담는 nodeDic을 생성
• nodeDIc 구조는 [A:[A와 연결된 노드들]] 
• 시작점을 바꿔가며 DFS를 이용하여 값이 다른(연결되지 않은) 부분들을 찾으려고 함 

DFS

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var nodeDic = [Int:[Int]]() // 인접한 노드들을 가지는 딕셔너리
    
    for i in 0..<computers.count{
        var arr = [Int]()
        for j in 0..<computers[i].count{
            if computers[i][j] == 1 && i != j{
                arr.append(j)
            }
        }
        nodeDic[i] = arr
    }
    //nodeDic 데이터 저장
    
    var network = [[Int]]()
    
    for i in 0..<n{
        let arr = dfs(dic: nodeDic, start: i).sorted(by: <)
        if !network.contains(arr){
            network.append(arr)
        }
    }
    return network.count
}

func dfs(dic: [Int:[Int]], start: Int) -> [Int]{
    var queue = [Int]()
    var stack = [start]
    
    while !stack.isEmpty{
        let node = stack.removeLast()
        if queue.contains(node){ continue}
        
        queue.append(node)
        stack += dic[node] ?? []
    }
    return queue
}