[Algorithm] Swift 전력망을 둘로 나누기 문제 풀이 [프로그래머스 Level2]

💬 문제

코딩테스트 연습 - 전력망을 둘로 나누기

---

💬 Idea

1. 첫번째 아이디어

• 아이디어 - 간선을 가장 많이 갖고있는 노드 사이를 끊자
• 결과 → 1,6,7 만 성공 ..

 

< 반례 >

반례 전력망 case

 

반례 전력망 case에서 가장 많은 간선을 갖고있는 노드는 1과 6이다. (각각 3개씩 갖고 있음)

 

 

[ case 1 ]

case1

 

case1처럼 1과 4 사이를 끊었을 때 -> 각 송전탑의 개수는 3개 / 5개로 차이는 2이 된다. (5-6 사이를 끊어도 동일)

 

 

📍 그러나, 이 case에서는 4와 5 사이를 끊는 것이 더 적은 차이값을 도출한다. 아래의 case2를 보자.

 

 

[ case 2 ]

case2

 

case2처럼 4와 5 사이를 끊었을 때 -> 각 송전탑의 개수는 4개 / 4개로 차이는 0이 된다. (case1보다 더 적은 차이값 도출 !)

 

따라서 첫번째 아이디어로 문제를 풀게 되면 대부분의 테스트케이스를 실패하게 된다..

 

 

2. ✅ 두번째 아이디어

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

---

💬 풀이

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에 반영
            result = distance < result ? distance : result
            
            // 🛠️ 전력망 복구
            route[i.key]?.append(j)
            route[j]?.append(i.key)
        }
    }
    
    return result
}

/// dfs 메서드
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
}

 

 

 

 

반례 참고: https://school.programmers.co.kr/questions/20917

프로그래머스

 

 

<풀이>

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Programmers/level2/%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84%20%EB%91%98%EB%A1%9C%20%EB%82%98%EB%88%84%EA%B8%B0.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift