코드

import Foundation

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 = n
    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 a = abs(bfs(route, i.key).count - bfs(route, j).count)
            // result 보다 작으면 저장
            result = a < result ? a : result
            
            // 전력망 복구
            route[i.key]?.append(j)
            route[j]?.append(i.key)
        }
    }
    
    return result
}

func bfs (_ route: [Int:[Int]], _ node: Int) -> [Int] {
    var visited = [Int]()
    var needVisit = [Int]()
    needVisit.append(node)
    
    while !needVisit.isEmpty {
        let now = needVisit.removeFirst()
        if visited.contains(now) {
            continue
        }
        visited.append(now)
        needVisit.append(contentsOf: route[now] ?? [])
    }
    
    return visited
}

회고

• 2단계치고 어렵다고 느껴졌다..
• 이런 노드들이 나오면 이해가 잘 되지 않아 풀지 못하는 것 같다
• 이런 유형의 문제가 나오면 이번 문제를 잘 떠올려야겠다