[알고리즘 연습] 전력망을 둘로 나누기 (프로그래머스 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를 매번 비교해가며 가장 작은 차이를 찾는다.