[dfs/백준] 1068번 : 트리

- 문제 : https://www.acmicpc.net/problem/1068

 

리스트 트리 구조로 바꾸고, visit 리스트 추가해서 진행했더니 메모리초과가 떠서 실패했던 문제 

굳이 이렇게 할 필요 없고, 주어진 리스트에 삭제된 노드 -2 처리하고, 리스트 값에 없는 값들이 자식 노드이므로 

자식노드이고, -2 처리가 안 된 인덱스 갯수를 센 후 출력하면 된다 

 

- 정답 풀이 : 

import sys
sys.setrecursionlimit(10**6)

n=int(input())
data=list(map(int,input().split()))
target=int(input())

def dfs(x,data):  
    data[x]=-2
    for i in range(n):
        if x==data[i]:
            dfs(i,data)
        
dfs(target,data)

count=0
for i in range(n):
    #삭제 되지 않은 자식 노드
    if data[i]!=-2 and (i not in data):
        count+=1
        
print(count)