[프로그래머스] 전력망을 둘로 나누기 (Swift)

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

프로그래머스

 

 

 

DFS

 

 

 

1. wires의 요소를 하나씩 제거한 뒤, 연결되어 있는 노드들을 파악

2. DFS 를 이용해 1부터 n숫자중 아무거나 대입 하였을 시 값과 

3. n - 2번의 값이 0이상이고 최소값일 경우 result를 수정

 

 

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    
    var result = n
    
    //1. wires의 요소를 하나씩 제거한 뒤, 연결되어 있는 노드들을 파악
    for i in 0..<wires.count {
        var graph: [Int:[Int]] = [:]
        var wireless = wires
        wireless.remove(at: i)
        
        var arr = [Int]()
        
        for j in 0..<wireless.count{
            graph[wireless[j][0]] = (graph[wireless[j][0]] ?? arr) + [wireless[j][1]]
            graph[wireless[j][1]] = (graph[wireless[j][1]] ?? arr) + [wireless[j][0]]    
        }
        
        2. DFS 를 이용해 1부터 n숫자중 아무거나 대입 하였을 시 값과 
        let a = dfs(graph, 1).count
        let b = n - a
        
        3. n - 2번의 값이 0이상이고 최소값일 경우 result를 수정
        if a >= b{
            if result > a - b{
                result = a - b
            }
        }
        else{
            if result > b - a{
                result = b - a
            }
        }
    }
    return result
}

func dfs(_ graph: [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 += graph[node] ?? []
    }
    
    return queue
}

 

 

실패코드

- 예제는 모두 맞출 수 있음

- wires에 차례로 접근할 경우 실제로 연결되어 있지만 setA에 포함되어 있지 않아 setB에 담겨 있는 경우가 생김

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    
    var result: Int?
    
    for i in 0..<wires.count{
        var arr = wires
        arr.remove(at: i)
        
        var setA = Set<Int>()
        var setB = Set<Int>()
        
        setA.insert(arr[0][0])
        setA.insert(arr[0][1])
        
        for j in 1..<arr.count{
            if setA.contains(arr[j][0]) || setA.contains(arr[j][1]){
                setA.insert(arr[j][0])
                setA.insert(arr[j][1])
            }
            else{
                setB.insert(arr[j][0])
                setB.insert(arr[j][1])
            }
        }

        if result == nil{
            if setA.count - setB.count >= 0{
                result = setA.count - setB.count
            }
            else{
                result = setB.count - setA.count
            }
        }
        else{
            
            if setA.count - setB.count >= 0 && setA.count - setB.count < result!{
                result! = setA.count - setB.count
            }
            if setB.count - setA.count >= 0 && setB.count - setA.count < result!{
                result! = setB.count - setA.count
            }
            
        }
        
    }
  
    return result!
}