[프로그래머스/Swift] 43162번 - 네트워크

🔗 문제 링크

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

💡 구현 아이디어

• 한 네트워크를 기준으로 확인하는 방법은 네트워크를 큐에 넣고 큐의 first와 연결된 네트워크를 전부 큐에 넣고 first를 dequeue 해주는 것을 반복한다. 이때 큐가 비면 연결된 한 네트워크를 찾은 것이다.
• 전체 네트워크를 돌면서 한 네트워크를 기준으로 찾는 방법을 계속 시행한다.
• 해당 아이디어를 발전 시키는 방법은 내가 확인한 네트워크를 저장하는 방법이 있다 예를 들어, A 네트워크와 연결된 B 네트워크를 큐에 넣고 B가 first 가 되어 연결된 네트워크를 찾았다고 한다면 B 네트워크는 전체 네트워크 에서는 제외해도 되는 것이다. 또한 A에서 B가 연결되어있는지 확인할 때 A→B 를 확인하고 B→A로 다시 A가 큐로 들어가기 때문에 조건에서 이전에 확인한 네트워크는 제외 시켜준다.
• 추가 아이디어) 네트워크 관계도를 그래프로 생각해보면 그래프는 양방향 트리로 생각할 수 있다. 그러면 현재 네트워크의 루트 노드를 하나의 네트워크로 바라보면 A→B, B→C 이면 A - → C 인 상황을 B의 루트는 A, C의 루트는 B이지만 B의 루트가 A라서 C의 루트를 A로 표현이 가능하다. 루트노드가 무엇이지에 대해 배열을 만들었다면 그것을 Set로 넘겨주면 중복이 사라지니 Set.count 만으로 네트워크 개수를 확인할 수 있을거 같다.

💻 코드

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
  var isCheck: [Bool] = [Bool](repeating: false, count: n)
  var queue: [Int] = []
  var queIdx: Int = 0
  var result: Int = 0
  
  for startIdx in 0..<computers.count {
    if isCheck[startIdx] == true { continue }
    
    queue.append(startIdx)
    while queIdx < queue.count { // 큐가 빌때까지 진행
      let netA = queue[queIdx]
      queIdx += 1
      isCheck[netA] = true
      for (idx, network) in computers[netA].enumerated() { // idx: 수신네트워크, network: 연결상태
        if network == 1 && !isCheck[idx] { // 수신네트워크는 검사를 안했으며 현재 네트워크와 연결되어있음
          queue.append(idx) // 네트워크를 큐에 추가
        }
      }
    }
    result += 1 // 네트워크 개수 +1
  }
  return result
}

⏳ 시간 복잡도

가장 바깥부터 반복문 1,2,3으로 정의

상황1) 모든 네트워크가 각자의 네트워크를 구성한 경우

• 반복문 1은 N번, 반복문 2는 1번, 반복문 3은 N번

상황2) 모든 네트워크가 연결된 네트워크를 구성한 경우

• 반복문 1은 1번, 반복문 2는 N번, 반복문 3은 N번

반복문 1의 반복횟수는 반복문 2와 반비례한다(1과 2을 합쳐서 N으로 보면 된다)

⇒ 전체 시간 복잡도는 O(N2)