[Python] 백준 1068번 : 트리

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

1068번: 트리

---

 문제 풀이

DFS 문제이다!

 

우선 입력받은 값들을 딕셔너리를 이용해서 그래프화 시킨다.

이미 값들은 그래프화 시켰기 때문에 지우는 것만 따지면 된다.

스택을 이용해서 DFS를 구현한다.

지울 노드를 스택에 넣고 그 자식들을 스택에 넣으면서 차근차근 지워주면 된다.

다 지웠다면 목표 노드의 부모 노드를 for문으로 찾아 리스트에서 지워주고 (N의 범위가 50까지라서 가능하다..!)

남아있는 딕셔너리 중 비어있고 키 값이 -1이 아닌 것을 세주면 된다.

 느낀 점

그렇게 어렵진 않았는데 문제를 제대로 안 읽어서 한 시간을 뻘짓했다.. 그리고 범위가 컸으면 틀렸을 지도..?

DFS같지 않고..? 잘 모르겠다, 이 문제는 썩 좋은 것 같진 않다.

 코드

import sys

def DFS(t):
    stack = [t]
    cnt = 0
    
    while stack:
        n = stack.pop()
        if n in d:
            stack.extend(d[n])
            del d[n]
            
    for k in d:
        if t in d[k]:
            d[k].remove(t)
            
    for k in d:
        if not d[k] and k != -1: 
            cnt += 1
    
    print(cnt)

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
t = int(sys.stdin.readline())
d = {}

for i, v in enumerate(arr):
    if i not in d: d[i] = []
    d[v] = d.get(v, []) + [i]
    
DFS(t)