백준 1068 트리 파이썬

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

1068번: 트리

일반적인 dfs탐색으로 문제를 풀어봤다.

def dfs(y):
    global re
    if g[y]==[-1]:#삭제 노드로 접근하면 return
        return
    for i in g[y]:
        if not vist[i]:#g[y]에 있는 노드로 접근
            vist[i]=True
            if g[i]==[]:#i 노드가 리프 노드이니 re+=1
                re+=1
            dfs(i)#리프 노드가 아닐 수 있으니 dfs(i)를 해줌으로 다시 탐색


n= int(input())
g = [[] for _ in range(n)]#트리 그래프
s = list(map(int,input().split()))
for i in range(n):
    if s[i]!=-1:
        g[s[i]].append(i)
    else:
        t = i#시작 지점 저장
en = int(input())#삭제 노드
re = 0
g[en]=[-1]#그래프에서 삭제노드를 -1로 해줌
vist = [False]*(n+1)#방문 기록
vist[t]=True
dfs(t)
if en!=t and re==0:#트리 노드만 남았을 경우를 예외처리
    print(1)
else:
    print(re)#리프 노드의 개수
#위 작업을 안 해주면 리프노드 == 트리노드인 경우을 카운트 못해요 아래는 예시입니다.
2
-1 0
1
답:1

위와 같은 방법으로 풀었더니 7X%정도 가서 틀렸습니다가 나와 뭐가 문제인지 고민해보니

9
-1 0 0 5 2 4 4 6 6
4

위와 같은 경우에 루트 노드에 연결된 1 and 2 가 리프 노드가 돼서 2를 출력해야 하는데 1을 출력하는 것을 발견했다.

g = [[1, 2], [], [4], [], [-1], [3], [7, 8], [], []]

(g[1]->[] 여서 re+=1 g[2]->g[4]->[-1]이여서 return)하지만 4번 노드는 제거 됐기에 2번 노드가 리프 노드임.

그래서 노드가 삭제돼 리프노드가 된 경우에도 re+=1해주게 한가지 작업을 더 해줘 AC를 받았다.

def dfs(y):
    global re
    for i in g[y]:
        if not vist[i] and i !=en:
            vist[i]=True
            if g[i]==[]:
                re+=1
            dfs(i)
        elif i==en and len(g[y])==1:#삭제된 노드때문에 리프노드가 된 경우!
            re+=1


n= int(input())
g = [[] for _ in range(n)]
s = list(map(int,input().split()))
for i in range(n):
    if s[i]!=-1:
        g[s[i]].append(i)
    else:
        t = i
en = int(input())
re = 0
g[en]=[]
vist = [False]*(n+1)
vist[t]=True
dfs(t)
print(re)
#트리 노드가 리프 노드인 경우를 더이상 예외처리 안 해도 됨