[프로그래머스/Swift] 86971번 - 전력망을 둘로 나누기

🔗 문제 링크

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

💡 구현 아이디어

1. 전선망을 하나씩 끊은 후 각 전선망의 전송탑의 개수를 확인
2. 가장 차이가 적게 나는 부분 반환
3. check 함수에서 단순히 전체 확인을 하지 않고 n에 연결된 전송탑을 딕셔너리로 정리하면 좀 더 깔끔하게 풀 수 있음

💻 코드

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
  var result = 1000
  for value in wires.enumerated() {
    var wires = wires
    let cutting = wires.remove(at: value.offset)
    let num = check(s1: cutting[0], s2: cutting[1], wires: wires)
    result = min(result, num)
  }
  return result
}

func check(s1: Int, s2: Int, wires: [[Int]]) -> Int {
  var wires = wires
  var wiresIdx = 0
  
  var arr1: [Int] = [s1]
  var arr2: [Int] = [s2]
  
  while wiresIdx < wires.count {
    let wire = wires[wiresIdx]
    wiresIdx += 1
    let element1 = wire[0]
    let element2 = wire[1]
    if arr1.contains(element1) {
      arr1.append(element2)
    } else if arr1.contains(element2) {
      arr1.append(element1)
    } else if arr2.contains(element1) {
      arr2.append(element2)
    } else if arr2.contains(element2) {
      arr2.append(element1)
    } else {
      wires.append(wire)
    }
  }
  return max(arr1.count, arr2.count) - min(arr1.count, arr2.count)
}

❌ 틀린 이유 및 틀린 부분

⏳ 시간 복잡도

O(n^2) - 완전탐색

📌 풀이 또는 기억할 정보