백준 1068 트리(DFS)

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

1068번: 트리

DFS를 이용하여 방문처리를 해준다음 풀어나가는 문제였다.

처음에 접근한 방식은 2중 그래프를 만들어서 각각 숫자에 누가 연결되어있는지 판단한 다음에

-1이 root node이기 때문에 -1부터 시작해서 DFS를 돌리고 len(graph[temp]) == 0일 때 자식노드가 없다는 것으로 판단하고 풀었는데 완전히 잘못된 생각이였다.

반례)

4 
-1 0 1 2 
2

처럼 모두 일직선으로 연결되어있는 트리를 보면 2에서 자르게 되면 1이 리프노드가 되어 답은 1이 되어야하는데 내가 짠 코드대로 해버리면 부모노드까지 잘라버려서 이상한 값이 나온다.

 

문제를 읽어보면 주어진 숫자의 의미는 내 부모노드가 어떤 숫자인지 가르쳐준다는 의미이다.

즉 주어진 숫자들은 어떤 i라는 숫자의 부모노드가 되야하기 때문에 리프노드가 될 수 없다

먼저 숫자들에 대해서 DFS를 돌릴껀데 k부터는 모두 없어져야하니까 k에 연결된 모든 것들은 연산에 영향을 미치지 않는 새로운 값으로 대입해준다.

 

즉, dfs(k, arr)를 해서 arr[k] = -2를 해주고 그 부모노드가 k인 node에 대해서 다시 DFS를 돌린다

 

이렇게 되면 최종적으로 k에 대한 제거가 끝나고 최종 array가 남을텐데

 

array에 0부터 len(array)까지 array에 포함되지 않은 수를 찾으면 된다.

why?)

array에 적힌 값은 어떤 수 i에 대한 부모노드가 적힌 리스트인데 0,1,2,...,len(arr)-1까지의 숫자들 중

예를들어 1이라고 하면 1이 array에 없다는건 어떤 수 i가 1을 부모노드로 가지고 있지 않다!

라는 것이고 즉 다른말로 말하면 1은 자식노드가 없다는 것이기 때문에 리프노드이다. 라는 것

 

import sys
input = sys.stdin.readline

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

n = int(input())
data = list(map(int, input().split()))
k = int(input())
res = 0

dfs(k, data)
for i in range(len(data)):
    if data[i] != -2 and i not in data:
        res += 1
print(res)