백준 파이썬 1068 트리

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

1068번: 트리

 

 

dfs로 푸는건 알겠는데 어떻게 탐색을 하지? 라는 생각을 계속 하다가 결국 다른 분의 코드 풀이를 보고

내 자신이 한심하다는 생각좀 잔뜩 하고나서 코드를 이해했다.

 

해당 그림을 트리 s 라고 가정하면 [-1,0,0,1,1] 이다. 이 경우에서 remove가 1일 경우에는

1을 포함한 모든 자식 노드까지 삭제를 해야하기 때문에 1을 따라 dfs를 실행하면 된다.

 

일단 삭제할 노드 부모인 1을 -2로 삭제했다는 표식을 남기고

만약 노드를 따라 탐색을 하는 도중 방금 삭제한 노드의 자식임이 확인된다면 그 노드를 부모로 가정하고

계속해서 dfs로 노드를 삭제시켜나가면 된다.

def dfs(x,arr):
    arr[x] = -2
    for i in range(n):
        if x == arr[i]:
            dfs(i,arr)

 

그렇게 되면 s = [-1, -2, 0, -2, -2] 라는 결과가 나오게 된다.

이 상태에서 for in문으로 완벽탐색을 하고나서 삭제표식인 -2와 자식 노드가 없음을 확인했다면 cnt += 1

 

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

cnt = 0

def dfs(x,arr):
    arr[x] = -2
    for i in range(n):
        if x == arr[i]:
            dfs(i,arr)

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

print(cnt)

 

 

알고보면 정말 쉬운문제인데 이걸 생각못했다는게 너무 한심