dictionary를 사용한 트리 구성
-1:[0]
0:[1,2]
2:[3,4]
4:[5,6]
6:[7,8]
dictionary 사용 이유
굳이 Tree구조를 만들고 탐색할 필요가 없음
list를 사용할 경우 입력받은 노드의 수(n)만큼의 2차원 배열을 생성해줘야함
import sys
input = sys.stdin.readline
from collections import defaultdict
# 입력값을 저장하고 트리를 구성할 defaultdict 생성
n = int(input())
li = list(map(int,input().split()))
m = int(input())
d = defaultdict(list)
# 입력값들로 dictionary를 이용한 트리 생성
for i in range(n):
d[li[i]].append(i)
def dfs(index):
# default로 list를 선언했기 때문에 자식으로 빈 배열을 가지고 있는 노드가 리프
if d[index] == []:
return 1
# 해당 노드까지의 리프 갯수(num)
num = 0
for i in d[index]:
# 탐색할 노드가 삭제할 노드라면 탐색을 진행하지 않는다.
if i==m:
# 자식 노드가 삭제할 노드뿐이라면 리프이기 때문에 1을 반환한다.
if len(d[index])==1:
return 1
continue
num += dfs(i)
return num
import sys
input = sys.stdin.readline
from collections import defaultdict
# 입력값을 저장하고 트리를 구성할 defaultdict 생성
n = int(input())
li = list(map(int,input().split()))
m = int(input())
d = defaultdict(list)
# 입력값들로 dictionary를 이용한 트리 생성
# 삭제하게될 노드와의 간선 절단
for i in range(n):
if i == m:
continue
d[li[i]].append(i)
def dfs(index):
# default로 list를 선언했기 때문에 자식으로 빈 배열을 가지고 있는 노드가 리프
if d[index] == []:
return 1
# 해당 노드까지의 리프 갯수(num)
num = 0
for i in d[index]:
num += dfs(i)
return num
print(dfs(-1))
if d[-1]==[]:
print(0)
else:
print(dfs(-1))
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
li = list(map(int,input().split()))
m = int(input())
d = defaultdict(list)
for i in range(n):
if i == m:
continue
d[li[i]].append(i)
def dfs(index):
if d[index] == []:
return 1
num = 0
for i in d[index]:
num += dfs(i)
return num
if d[-1]==[]:
print(0)
else:
print(dfs(-1))
dictionary를 이용한 트리 구성 - O(n)
dfs 함수를 이용한 리프 노드 탐색 - O(n)