BOJ 1068번: 트리

www.acmicpc.net/problem/1068

1068번: 트리

아이디어:

이거를 틀렸었나 보다.. 주어진 입력만 사용하지 말고 새롭게 child배열을 만들어서 풀면 간단히 풀 수 있는 문제였다.

일단 input의 부모배열을 가지고 child배열을 만들어 저장하고, 그 배열을 이용하여 DFS탐색을 한다.

이때 탐색하는 n이 삭제할 노드와 같다면 상황을 나누어야 하는데, n의 부모 노드의 자식이 n 하나 뿐이라면 부모노드도 리프노드가 되므로 cnt+=1을 해주고 그 외의 경우에는 그냥 continue한다.

 

import sys
N = int(sys.stdin.readline())
parent = list(map(int, sys.stdin.readline().split()))
delete = int(sys.stdin.readline())
#자식노드의 개수
child = [[] for _ in range(N)]
root = -1
for i in range(N):
    if (parent[i]==-1):
        root = i
        continue
    child[parent[i]].append(i)

visit = [False]*(N)
cnt = 0
stack = []
stack.append(root)

while (stack):
    n = stack.pop()
    visit[n]=True
    if (n==delete):
        if (len(child[parent[n]])==1): #n의 부모노드가 리프노드가 되는 경우
            cnt+=1
        continue
        
    if (len(child[n])==0): cnt+=1
    
    for i in child[n]:
        if (visit[i]==False):
            visit[i] = True
            stack.append(i)
print(cnt)