[백준/파이썬] 1068 트리

#문제링크

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

1068번: 트리

#나의풀이

import sys
from collections import defaultdict

def find(num):
    global answer
    for value in tree[num]:
        if value in tree:
            find(value)
        else:
            answer += 1
            
if __name__=="__main__":
    N = int(sys.stdin.readline())
    tree = defaultdict(list)
    arr = list(map(int, sys.stdin.readline().split()))
    delete_node = int(sys.stdin.readline())
    arr[delete_node] = -2147000000
    answer = 0
    for i in range(N):
        tree[arr[i]].append(i)

    find(-1)

    print(answer)

#해설

제목 그대로 트리문제이고 리프노드 개수를 구하는 문제이다. 골드5 치고 상당히 쉬웠는데 트리라서 감안해서 레벨을 받은거 같다.

 

N = int(sys.stdin.readline())
    tree = defaultdict(list)
    arr = list(map(int, sys.stdin.readline().split()))
    delete_node = int(sys.stdin.readline())
    arr[delete_node] = -2147000000
    answer = 0
    
    for i in range(N):
        tree[arr[i]].append(i)

    find(-1)

입력받는 부분이다 tree 는 defaultdict로 받았는데 기존 파이썬 딕셔너리를 쓰다보면 값이 없을때 append시 에러가 나는데 defaultdict은 이부분을 해결해줘서 편하게 쓸 수 있어 사용했다

이후 delete되는 노드를 받고 배열에서 delete된 부분을 다시 접근 못하도록 접근하지 못하는 부모값으로 설정해주었다.

tree에는 i의 값의 부모노드를 key값으로 해서 append해 넣어주었다.

 

def find(num):
    global answer
    for value in tree[num]:
        if value in tree:
            find(value)
        else:
            answer += 1

재귀로 탐색한다. tree에 key값이 num인 애들을 value로 설정하여 돌며 tree에 value로 된 키값이 있다면 부모노드가 되는것이므로 다시 finde에 넣어 탐색해주었고 아닐경우 리프노드이므로 결과값에 +1을 해주었다.