BOJ [트리]

문제

2022-03-29

문제보기

이런식으로 tree랑 지울 노드가 주어진다.

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다.

만약 부모가 없다면 (루트) -1이 주어진다.

셋째 줄에는 지울 노드의 번호가 주어진다

tree 에서 해당 노드와 그밑에 자식들까지 싹 지운후 남는 트리의 leaf노드를 구하시오.

아이디어

일단 이진트리가 아니므로 tree class에서 tree.son 을 리스트로 선언했다.

class에서 list선언 가능하다

코드

n = int(input())
tree = []

while len(tree) < n:
  tree += list(map(int,input().split()))

del_index = int(input())

class Tree:
  def __init__(self,data,list):
    self.son = []
    if data != -1:
      self.data = data
      for i in range(len(list)):
        if list[i] == data:
          self.son.append(Tree(i,list))
    else:
      for i in range(len(list)):
        if list[i] == data:
          self.data = i
          for j in range(len(list)):
            if list[j] == i:
              self.son.append(Tree(j,list))
          break

tree = Tree(-1,tree)
isDone = False

def postorder_del(tree,x):
  global isDone
  if isDone:
    return
  for i in range(len(tree.son)):
    if tree.son[i].data == x:
      del tree.son[i]
      isDone = True
      break
  if isDone:
    return
  for i in range(len(tree.son)):
    postorder_del(tree.son[i],x)

postorder_del(tree,del_index)

count = 0

def postorder_check(tree):
  global count
  if len(tree.son) == 0:
    count+=1
    return
  else:
    for i in range(len(tree.son)):
      postorder_check(tree.son[i])

postorder_check(tree)

if del_index == tree.data:
  print(0)
else:
  print(count)