백준 1068 트리

출처: www.acmicpc.net/problem/1068

분류: 트리

---

접근방식

전형적인 트리 문제였습니다.

주어진 대로 부모자식을 쭉 연결한 다음 dfs나 bfs 방식으로 탐색하다가 삭제해야 할 노드를 만나면 건너뛰는 방식으로 하면 해당 요구조건에 맞게 빠르게 해결할 수도 있으나 (많은 분들이 그렇게 푸신 것 같습니다.)

저는 실제 트리에 가깝게 해결해보고 싶어서 실제로 해당 노드와 그 자식 노드들을 제거해주는 방식으로 해결해봤습니다. 

처음에는 Node, Tree 클래스를 각각 만들어서 처리해서 풀었다가 별도의 Tree 클래스 없이 루트노드만 가지고 해결하도록 개선해봤는데요,

n만큼 임시 배열에 노드를 만들어두고 -1을 만나면 treeNode의 변수로 저장해두고 연결과 제거를 모두 끝내고 나면
임시 배열을 날리고 treeNode의 leaf 개수를 세줬습니다. treeNode가 nil이면 0을 출력하도록 했구요 :)

 

추가적으로 -1을 만나면 treeNode로 지정해줬던 것처럼, 꼭 첫 번째 노드가 루트노드가 아니라는 점에 주의하셔야 합니다!
처음에 -1이 당연히 루트노드인 줄 알고 접근했다가 틀렸었네요.. -_ㅠ

 

해결방법

n = Int(readLine()!)!

class Node {
  var value: Int
  var parents: Node?
  var children = [Node]()

  init(_ value: Int) {
    self.value = value
  }

  func addChild(_ child: Node) {
    children.append(child)
    child.parents = self
  }

  func removeFromParents() {
    if let index = parents?.children.firstIndex(where: { $0.value == value }) {
      parents?.children.remove(at: index)
    }
  }

  func removeAllChilds() {
    children.forEach { $0.removeAllChilds() }
    children.removeAll()
  }

  func leafCount() -> Int {
    guard !children.isEmpty else { return 1 }
    var count = 0
    children.forEach {
      count += $0.leafCount()
    }
    return count
  }
}

let parentIndies = readLine()!.split(separator: " ").map({ Int(String($0))! })
var nodeTemps = [Node]()
(0..<n).forEach {
  nodeTemps.append(Node($0))
}
var treeNode: Node?

for (current, parents) in parentIndies.enumerated() {
  if parents == -1 {
    treeNode = nodeTemps[current]
  } else {
    nodeTemps[parents].addChild(nodeTemps[current])
  }
}

let remove = Int(readLine()!)!
nodeTemps[remove].removeAllChilds()
nodeTemps[remove].removeFromParents()
if nodeTemps[remove].value == treeNode?.value ?? -1 {
  treeNode = nil
}
nodeTemps.removeAll()

print(treeNode?.leafCount() ?? 0)

 

배운점

오랜만에 트리를 하니까 또 머리가 안 돌아간다....

그래도 단순히 DFS나 BFS로 풀고 남어간 것보다 많이 배웠던 것 같다 :)