Baekjoon 1068번 트리

문제

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

걸린 시간

02 : 03 : 01

풀이

Python3

class Node():
    def __init__(self, item):
        self.item = item 
        self.link = []

# 지워야 할 노드의 부모 탐색
def search(root, item):
    for i in root.link:
        if i.item == item:
            return root

    succ = None

    if root != None:
        for i in root.link:
            obj = search(i, item)
            if obj != None:
                succ = obj

    return succ 

# 단말 노드의 개수 찾기
def get_leaf(root):
    count = []

    if root != None:
        # 자식 노드가 없으면, 단말노드이면
        if len(root.link) == 0:
            return 1

        # 자식 노드가 있으면    
        for i in root.link:
            count.append(get_leaf(i))

    return sum(count)

if __name__ == "__main__":
    # 트리의 노드 개수
    N = int(input())    

    node_p = list(map(int, input().split()))
    node = []
    node_obj = []

    # 노드의 번호와 부모의 번호 쌍
    for i in range(0, N):
        node.append([i, node_p[i]])

    # 입력받은 만큼 노드 객체를 생성    
    for i in range(0, N):
        node_obj.append(Node(i))

    # 노드 객체들을 입력받은 정보로 연결 
    for i in range(0, N): 
        # 루트 노드이면
        if node[i][1] == -1:
            root = node_obj[i]
        else:
            node_obj[node[i][1]].link.append(node_obj[i])

    # 지울 노드의 번호
    D = int(input())

    # 지워야할 노드의 주소를 갖고 있는 부모의 link 리스트에서 값을 삭제해야함.
    obj = search(root, D)

    # 루트 노드는 검색되지 않음, None 일 경우 루트 노드를 삭제
    if obj == None:
        root = None
    else:
        for i in range(0, len(obj.link)):
            if obj.link[i].item == D:
                del obj.link[i]        
                break

    print(get_leaf(root))

0번부터 N-1번까지의 노드를 부모노드 정보와 함께 입력받는다.

같은 부모를 여럿이 가질 수 있기 때문에 이진 트리가 아닌 n진트리 형태이다.

모든 노드를 객체화 시키고 입력받은 정보로 알맞은 부모와 자식끼리 연결시켜 트리를 완성시켰다.

세번째 줄 입력으로는 삭제할 노드가 주어진다. 다행인것은 삭제할 노드의 자식까지 모두 제거하도록 조건이 쉽게 주어졌다는 점이다.

그럼에도 순환함수의 흐름을 이해하기가 쉽지 않아 구현하는데 꽤나 오랜 시간이 걸렸다.