[백준/dfs] 1068번: 트리

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

Gold level 5문제다 

 

문제를 이해한 것으로는 1. 노드를 없애고 2. 자식 노드를 구별해서 그것의 갯수를 구해야한다고 생각했다. 

1번을 구체적으로 하자면

처음 지운 노드의 모든 자식노드들도 삭제되어야 하므로 그들의 인덱스 값에 -2를 대입해야하는데, 이때 dfs를 사용해야한다고 생각했다.

-2를 넣은 이유는 -1은 루트 노드를 가리키기 때문에 다른 숫자로 삭제 노드를 표현해야 했다 

배열 전체를 탐색하며, 방금 삭제한 인덱스를 부모로 가지는 노드를 찾아 dfs함수를 재귀호출한다 

 

2번을 구체적으로 하자면 

dfs로 노드들을 삭제한 뒤 삭제되지 않고 남은 트리에서 자식노드를 구해서 그것의 갯수를 구하면 된다 

 

이 문제에서 나는 1번을 구현하는 것이 어려웠던 것 같다. 2번은 비교적 쉬웠다 

 

-정답풀이: 

n=int(input())
s=list(map(int,input().split()))
k=int(input())

#k노드 지우고 트리 정리
def dfs(v,s):
    s[v]=-2
    for i in range(n):
        if v==s[i]: #v가 부모노드일때
            dfs(i,s) #v의 자식노드들도 삭제하기 
        

dfs(k,s)     
cnt=0        
for i in range(n):
    if s[i]!=-2 and (i not in s):
        cnt+=1
print(cnt)

-틀린 풀이 피드백:

dfs에서 초기값을 넣으면 그 값부터 -2로 바뀐 후 진행되므로 15-19라인은 굳이 필요 없었다. 이 내용을 dfs 구현 내용에 넣으면 된다(물론 둘다 코드는 틀렸다)

그리고 22-25라인은 필요 없다. 왜냐하면 이미 주어진 리스트 s의 값들이 부모노드를 의미하므로 굳이 parent라는 리스트를 따로 만들어서 값을 넣을 필요는 없다 -2가 아니면 다 부모 노드이므로.