[알고리즘 연습] 전력망을 둘로 나누기 (프로그래머스 lv2, 스위프트)

문제

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

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

풀이

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var connect = Array(repeating: Array(repeating: false, count: n+1), count:n+1)

    wires.forEach {
        connect[$0[0]][$0[1]] = true
        connect[$0[1]][$0[0]] = true
    }

    var minCount = Int.max

    func count(startFrom startIndex: Int) -> Int {
        var visited = Array(repeating: false, count: n+1)
        visited[startIndex] = true
        var stack = [startIndex]
        var count = 1
        while stack.count > 0 {
            let now = stack.removeLast()
            for (index, connected) in connect[now].enumerated() {
                if connected && !visited[index] {
                    visited[index] = true
                    stack.append(index)
                    count += 1
                }
            }
        }
        return count
    }

    wires.forEach {
        connect[$0[0]][$0[1]] = false
        connect[$0[1]][$0[0]] = false
        let result1 = count(startFrom: $0[0])
        let result2 = count(startFrom: $0[1])
        connect[$0[0]][$0[1]] = true
        connect[$0[1]][$0[0]] = true
        minCount = min(minCount,abs(result1-result2))
    }

    return minCount
}

• 너무 어렵게 생각하면 안되는 문제였다. 더 좋은 방법을 고민하다가 시간을 버렸다.
• 단순히 모든 길목을 막으면서 연결된 노드를 매번 확인하면 된다.
• minCount를 매번 비교해가며 가장 작은 차이를 찾는다.