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

프로그래머스 LV2. 전력망을 둘로 나누기 

 

✅ 이거 왜 포스팅 하냐면 두가지 의의가 나한테 있음.

1. 구글링 없이 BFS / DFS를 기반으로 알고리즘을 생각해내어서 문제를 해결함.

2. minValue를 계산하는 수식이 틀려서, 알고리즘이 맞음에도 뭐가 문제인지 고민한 시간들이 답답해서

 

문제가 되는 부분은 minValue를 업데이트 하는 과정에서 n - count - count를 해야하는데, 어떻게 생각했는지, count - n 이랑 동일한 값이라고 생각했음. 그래서 수정완료!!

 

✅ 코드 및 알고리즘 접근법

알고리즘 접근법은, input의 경우에는 늘 그랬듯 저렇게 받는다. 저렇게 받아야 각 정점(노드)들이 연결되어 있는게 빠지지 않고 설정된다.

 

그 다음에는 이중 for문을 사용하는데, 상위 for문에서는 정점을 순회하며하위 for문에서는 그 정점이 연결되어 있는 값을 순회한다.

 

여기서 중요한 로직이 이 문제의 조건에서 트리를 전제한다는 것인데, 그 정점에서 removeFirst()를 사용하여 끊어주면, 끊어진 반대편을 절대로 방문할 수 없게 된다.(단, 문제가 그래프일수도 있을 경우에는 이 알고리즘의 경우 반대쪽 정점(노드)에서도 끊어주는 작업이 필요하다.)

DFS를 사용하여 해당 정점을 기준으로 방문한다. 그럼 끊어진 부분을 방문하지 못해서 DFS의 값이 정점의 총 개수보다 작게 나올탠데, 이를 통하여 해결한다.

    func solution(_ n:Int, _ wires:[[Int]]) -> Int {
        var list = [Int :[Int]]()
        for i in 0..<wires.count {
            let start = wires[i][0]
            let end =  wires[i][1]
            
            if list[start] == nil {
                list[start] = [end]
            } else {
                list[start]?.append(end)
            }
            
            if list[end] == nil {
                list[end] = [start]
            } else {
                list[end]?.append(start)
            }
        }
        
        // 1. 전력망을 끊는다.
        // 2. DFS / BFS를 사용하여 방문한 지점을 카운팅한다.
        // 3. 최소값을 계산한다.
        var minValue = Int.max
        
        for i in 1...n {
            for _ in 1...list[i]!.count {
                let point = list[i]!.removeFirst() // 전력망 끊기
                
                if point != i {
                    let count = DFS(graph: list, start: i).count
                    minValue = min(abs(n - count - count), minValue)
                }
                list[i]!.append(point)
            }
        }
        
        
        return minValue
    }
    
func DFS<T> (graph: [T: [T]], start: T) -> [T] {
    var visitedQueue: [T] = []
    var needVisitStack: [T] = [start]
    
    while !needVisitStack.isEmpty {
        let node: T = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitStack += graph[node] ?? []
    }
    
    return visitedQueue
}

 

문제를 풀고나서 다른 분들은 어떻게 풀으셨는지 찾아보았음. 어떤 분이 엄청 세련되기 풀으신 코드가 기억남. 근데 나는 스탠다드와 오리지널하게 나만의 풀이법을 갖고 가는게 좋아서, 이렇게 품.