[Algorithm] 전력망을 둘로 나누기

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 전력망을 둘로 나누기](https://school.programmers.co.kr/learn/courses/30/lessons/86971)

💬 Idea

첫번째 풀이

• 아이디어 - 간선을 가장 많이 갖고있는 노드 사이를 끊자

• 결과 → 1,6,7 만 성공 ..

• 반례 → 이 case에서 가장 많은 간선을 갖고있는 노드는 3 or 6이다.

  

  • 3과 5 사이를 끊었을 때: 3 / 6으로 차이값은 3이 된다. (6-7 사이도 동일)
  • 그러나, 이 case에서는 4와 5 사이나, 4와 6 사이를 끊는 것이 더 적은 차이값을 도출한다.
  • 따라서 이 아이디어로 문제를 풀게 되면 대부분의 테스트케이스를 실패하게 된다.

두번째 풀이

• 아이디어 - 그래프를 돌면서 전력망을 하나씩 끊어보자 (완전탐색)
• 전력망을 끊은 후 - dfs로 네트워크의 수를 구한 후 차이값을 도출하고 - 전력망을 다시 연결해주는 것을 반복한다.
  • 만약 6과 7사이를 끊는다면, 전력망을 끊은 후 dfs로 6, 7 각각의 수에서 출발하였을 때 송전탑의 개수를 도출하여 차이값을 구한다.

💬 풀이

첫번째 풀이 (실패)

func solution(n:Int, wires:[[Int]]) -> Int {
    var v1: [Int: [Int]] = [:]
    for wire in wires {
        if v1[wire[0]] != nil {
            v1[wire[0]]?.append(wire[1])
        } else {
            v1[wire[0]] = [wire[1]]
        }
        
        if v1[wire[1]] != nil {
            v1[wire[1]]?.append(wire[0])
        } else {
            v1[wire[1]] = [wire[0]]
        }
    }
    
    let maxkey = v1.sorted(by: { $0.value.count > $1.value.count }).first!.key
    var cnt = (0,0)
    
    for i in v1[maxkey]! {
        cnt.0 = v1[i]!.count >= cnt.1 ? i : cnt.0
        cnt.1 = v1[i]!.count >= cnt.1 ? v1[i]!.count : cnt.1
    }

    v1[maxkey] = v1[maxkey]?.filter({ $0 != cnt.0 })
    v1[cnt.0] = v1[cnt.0]?.filter({ $0 != maxkey })
    
    var v2: [Int: [Int]] = [:]
    v2[cnt.0] = v1[cnt.0]
    
    v1[cnt.0]?.forEach { k in
        v2[k] = v1[k]
        v1 = v1.filter({ $0.key != k })
    }
    v1 = v1.filter({ $0.key != cnt.0 })
    
    return abs(dfs(v1, v1.first!.key).count - dfs(v2, v2.first!.key).count)
}

func dfs(_ arr: [Int: [Int]], _ n: Int) -> [Int] {
        var visitedQueue: [Int] = []
        var needVisitStack: [Int] = [n]
        
        while !needVisitStack.isEmpty {
            let node: Int = needVisitStack.removeLast()
            if visitedQueue.contains(node) { continue }
            
            visitedQueue.append(node)
            needVisitStack += arr[node] ?? []
        }
        
        return visitedQueue
}

두번째 풀이

func solution(n:Int, wires:[[Int]]) -> Int {
    var route: [Int: [Int]] = [:]

		// 그래프 만들기
    for wire in wires {
        if route[wire[0]] != nil {
            route[wire[0]]?.append(wire[1])
        } else {
            route[wire[0]] = [wire[1]]
        }
        
        if route[wire[1]] != nil {
            route[wire[1]]?.append(wire[0])
        } else {
            route[wire[1]] = [wire[0]]
        }
    }
    
    var result = wires.count
    for i in route {
        for j in i.value {
            // 끊기
            route[i.key] = route[i.key]!.filter({ $0 != j })
            route[j] = route[j]!.filter({ $0 != i.key })
            
            let distance = abs(dfs(route, i.key).count - dfs(route, j).count)
            result = distance < result ? distance : result
            
						// 복구
            route[i.key]?.append(j)
            route[j]?.append(i.key)
        }
    }
    
    return result
}

func dfs(_ arr: [Int: [Int]], _ n: Int) -> [Int] {
    var visitedQueue: [Int] = []
    var needVisitStack: [Int] = [n]
    
    while !needVisitStack.isEmpty {
        let node: Int = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitStack += arr[node] ?? []
    }
    
    return visitedQueue
}