[백준]1068(파이썬) - 트리

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

1068번: 트리

• 나는 알고리즘문제를 풀 때 트리관련 문제가 나오면 트리 구조를 확실하게 이해하고, 대부분을 리스트 형태로 구현한다.
• 이번 문제에서 핵심은 입력받은 del_node(삭제 노드)의 자식 노드들을 모두 없애고 리프노드를 구할 때, del_node까지만 고려해주면 되는 문제이다. 굳이 다 만들고, del_node의 자식들을 모두 지워주는 것은 비효율적이다.
• DFS로 구현하였고, 입력받은 graph값을 for문으로 tree리스트를 트리구조형태로 만들어주었다.
• tree리스트의 x번째 있는 원소들을 for문을 돌려주면서 재귀를 사용해서 DFS를 구현했고, DFS함수안에는 조건문을 달아서 cnt 값을 더해주었다.
• 자세한 코드는 아래 주석을 참고하면 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2500)
n = int(input())
graph = list(map(int,input().split()))
del_node = int(input())

tree = [[] for _ in range(n+2)]
for i in range(n):
    if graph[i] == -1:
        tree[n+1].append(i)
    else:
        tree[graph[i]].append(i)
def dfs(x):
    global cnt
    # tree[x]가 빈 리스트이면 자식 노드가 없다는 뜻 -> 리프노드라는뜻
    if len(tree[x]) == 0:
        cnt += 1
        return cnt
    for i in range(len(tree[x])):
        if tree[x][i] == del_node:
            # 만약에 원소가 하나라면 del_node랑 같을경우 del_node자식 노드를 다지우면 
            # del_node 부모노드라 리프노드가 되니까 +1 해준다.
            if len(tree[x]) == 1:
                cnt += 1
                return cnt
            else:
                continue
        else:
            dfs(tree[x][i])

cnt = 0
if graph[del_node] == -1:
    print(0)
else:
    # dfs(0)으로 계속 시도헀었는데 틀렸던 이유는
    # 처음 -1인 노드가 0번째가 아닐수도 있기 때문이다.
    dfs(n+1)
    print(cnt)