1068_트리

입력

첫째 줄에 노드의 개수 입력
둘째 줄에 각 노드의 부모 노드의 정보 입력
셋째 줄에 제거할 노드 정보 입력

출력

셋째 줄에 입력받은 노드를 제거했을 경우 리프 노드의 개수를 출력

조건

• 입력받는 노드의 개수는 1~50개
• root 노드가 첫번 째 노드가 아닐 수 있음

풀이

한 노드를 제거했을 경우 그 밑의 자식 노드들을 제거하여 남은 노드 수를 출력하는 풀이 방법
제거된 노드의 data 값을 -2로 설정하고 최종적으로 노드의 data != -2 & 자식 노드의 개수 == 0 인 조건을 만족하는 노드를 체크
깊이 우선 탐색(dfs)를 사용하여 풀이

1. tree를 리스트로 생성하고 각 노드의 data 값과 부모 노드 정보, 자식 노드 정보를 설정

tree = [Node(idx) for idx in range(N)]
for idx in range(N):
    parent = info[idx]
    tree[idx].parent = parent

    if parent != -1: tree[parent].child.append(idx)

2. 제거할 노드의 data 값을 -2로 설정하고 해당 노드의 부모 노드에서 자식 노드 정보를 pop
   제거할 노드의 자식 노드를 스택에 push

dq = deque([target])

while dq:
    node = dq.pop()
    
    if tree[node].data == -2: continue
    else:
        if not tree[node].parent == -1:
            parent = tree[node].parent
            child_idx = tree[parent].child.index(node)
            tree[parent].child.pop(child_idx)

        tree[node].data = -2
        for child in tree[node].child: dq.append(child)

3. 노드의 data가 -2가 아니고 자식 노드가 없는 노드의 개수를 체크

for idx in range(N):
    if tree[idx].data != -2 and len(tree[idx].child) == 0: ans += 1

전체 코드

트리