[알고리즘] Swift -프로그래머스 연습문제 #86971(전력망을 둘로 나누기) -BFS

문제링크

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

프로그래머스

 

 

 

 

 

분석

송전탑이 전선을 통해 하나의 트리 형태로 연결

 당신은 이 전선들 중 하나를 끊어서 현재 전력망 네트워크 2개로 분할하려고 한다

 이 때 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다

 

 송전탑의 개수 n 그리고 전선 정보 wires가 매개변수로 주어질 때

 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때

 두 전력망이 가지고 있는 송전탑 개수의 차이를 리턴하라

 

풀이

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var result = Int.max
    var map: [Int: [Int]] = [:]
    var check = Array(repeating: false, count: n+1)
    
    for i in 1..<n+1 {
        map[i] = []
    }
    
    for wire in wires{
        map[wire[0]]?.append(wire[1])
        map[wire[1]]?.append(wire[0])
    }
    
    func bfs(_ n: Int) -> Int {
        var arr = [Int]()
        var count = 0
        
        arr.append(n)
        check[n] = true
        
        while !arr.isEmpty {
            let pop = arr.removeFirst()
            count += 1
            
            for i in map[pop]! {
                if !check[i] {
                    arr.append(i)
                    check[i] = true
                }
            }
        }
        return count
    }
    
    for i in 1..<n+1 {
        check = Array(repeating: false, count: n+1)
        check[i] = true
        let cnt = bfs(1)
        result = min(result, abs(cnt - (n-cnt)))
    }
    
    return result
}

 

결과

 

 

 

---

📂  정리

bfs를 통해서 연결된 노드의 수를 구하는 문제이다.

하지만 차이점은 하나의 노드를 끊어서 체크하는 조건이 추가되었다.