[DFS] 백준 9466번: 텀 프로젝트(Swift)

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

난이도

골드 3

사용언어

Swfit

카테고리

DFS

풀이과정

텀 프로젝트 문제는 원형 트리가 생기면 그 노드끼리 팀이 형성되고, 최종적으로 팀에 속하지 못한 노드의 수를 구하는 문제이다.

문제의 핵심은 사이클이 형성된 노드의 개수를 구하는 것이다.
(사이클이 형성됐다. == 특정 노드가 2번 탐색되었다.)

때문에 visited 배열 변수를 두어 탐색이 된 노드인지 아닌지 판별한다.

탐색되지 않은 노드이면, 탐색을 이어가고, 이미 탐색이 된 노드이면, 사이클이 형성되었기 때문에 사이클에 포함 되는 노드의 수를 계산해 준다.

(예를들어, 1->2->3->4->1 => 1, 2, 3, 4가 한팀이 된다. 때문에 count = 4)

또한, 이미 팀이 형성된 노드거나, 팀에 포함되지 못한 노드는 두 번 탐색할 필요가 없기 때문에, done 배열 변수를 두어 중복 탐색되는 것을 막아 시간 복잡도를 낮춰줄 수 있다.

때문에 if OR else if 로직이 끝나고 해당 노드의 done값에 true를 저장한다.

Code

let t = Int(readLine()!)!
var results = [Int]()

for _ in 0..<t {
  let r = Int(readLine()!)!

  let choice = [0] + readLine()!.split(separator: " ").map { Int($0)! }
  
  if choice == Array(0...r) {
    results.append(0)
    continue
  }
  
  var visited = Array(repeating: false, count: r + 1)
  var done = Array(repeating: false, count: r + 1)
  var count = 0

  func dfs(start: Int) {
    visited[start] = true
    var n = choice[start]
    
    if !visited[n] {
      dfs(start: n)
    } else if !done[n] {
      while n != start {
        count += 1
        n = choice[n]
      }
      count += 1
    }
    done[start] = true
  }

  for i in 1...r {
    if !visited[i] {
      dfs(start: i)
    }
  }
  results.append(r - count)
}

results.forEach {
  print($0)
}