1068 - 트리
정보
- 문제 보기: 1068 - 트리
- 소요 시간: 49분
- 풀이 언어:
python
- 체감 난이도: 2️⃣~3️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
자료구조
트리
dfs
풀이 코드
정보
- 메모리: 31120 KB
- 시간: 40 ms
import sys
input = sys.stdin.readline
children = []
def dfs(cur, target):
cnt = 0
if cur == target:
return 0
if not children[cur]: # leaf
return 1
for nxt in children[cur]:
cnt += dfs(nxt, target)
if not cnt: # not leaf but none found -> just became leaf
cnt += 1
return cnt
def solution():
global children
n = int(input())
data = [int(x) for x in input().rstrip().split(' ')]
children = [[] for _ in range(n)]
root = -1
for i, parent in enumerate(data):
if ~parent:
children[parent].append(i)
else:
root = i
target = int(input())
print(dfs(root, target))
if __name__ == '__main__':
solution()