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

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var graph: [[Int]] = Array(repeating: [], count: n + 1)
    var visited = [Bool]()
    var answer = 100000
    
    // 인접 리스트로 저장
    for wire in wires {
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])
    }
    
    func dfs(_ vertex: Int, _ no: Int, _ count: inout Int) {
        visited[vertex] = true
        
        for next in graph[vertex] {
            if !visited[next] && next != no {
                count += 1
                dfs(next, no, &count)
            }
        }
    }
    
    for wire in wires { // 하나씩 다 끊어보기
        visited = Array(repeating: false, count: n + 1)
        var num1 = 1, num2 = 1
        dfs(wire[0], wire[1], &num1)
        
        visited = Array(repeating: false, count: n + 1)
        dfs(wire[1], wire[0], &num2)
        
        answer = min(answer, abs(num1 - num2))
    }
    
    return answer
}

n의 최대 개수가 100으로 매우 적기 때문에 완전 탐색을 사용해서 모든 경우의 수를 확인해도 된다.

wires 에 저장된 모든 전선을 차례대로 하나씩 끊어보고, 두 전력망의 송전탑(노드) 개수를 확인하기 위해 v1번 송전탑과 v2번 송전탑을 시작으로 각각 dfs를 수행한다.

그리고 두 dfs를 통해 얻은 송전탑 개수의 차의 절대값과 현재 answer 배열에 저장된 값을 비교하는 과정을 반복해서 최종 답을 구한다.