[DFS] 백준 1068번: 트리(Swift)

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

1068번: 트리

난이도

골드 5

사용언어

Swfit

카테고리

DFS

풀이과정

해당 문제는 트리의 Node중 하나가 지워졌을 때 마지막 노드(리프 노드)를 탐색하는 문제이다.

때문에 childNode로 해당 노드의 자식 노드를 배열에 저장해 탐색한다.

하지만, 탐색전 입력받은 노드를 제거 후 탐색해야 하기 때문에 target(삭제할 노드)를 통해 parentNode를 검색하고, 해당 값으로 childNode 배열에 접근해 targetNode를 제거 한다. 그러면 자연 스럽게 문제 조건에 맞게 targetNode의 자식 노드 또한 탐색 할 수 없게 된다.

하지만, targetNode가 루트 노드 이면 굳이 탐색할 필요 없이 0을 리턴해준다.

마지막으로 리프 노드를 찾는 방법은 간단하게 childNode가 없으면 리프 노드가 된다.

Code

let n = Int(readLine()!)!
var start: Int!
let parentNode = readLine()!.split(separator: " ").map { Int($0)! }
var childNode: [[Int]] = Array(repeating: [], count: n)
let target = Int(readLine()!)!
var result = 0

for i in 0..<parentNode.count {
  if parentNode[i] == -1 {
    start = i
    continue
  }
  childNode[parentNode[i]].append(i)
}

func solution() {
  if parentNode[target] == -1 {
    print(0)
    return
  } else {
    childNode[parentNode[target]].removeAll { $0 == target }
  }
  dfs(start: start)
  print(result)
}

func dfs(start: Int) {
  if childNode[start].count == 0 {
    result += 1
    return
  }
  
  for next in childNode[start] {
    dfs(start: next)
  }
}

solution()