[Python/미해결] 백준 1068번 문제, 트리

<문제 링크>

 

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

1068번: 트리

 

---

<풀이>

 

<! 아직 미해결된 문제입니다>

 

문제에서는 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력하는 것이다.

 

트리 구조를 class를 통해 만든 다음에 remove_target와 같은 값을 가진 노드를 삭제했다.

 

그렇다면 탐색을 통해 리프 노드의 개수를 구하기만 하면 된다.

따라서 전위 순회를 통해 순차적으로 노드를 확인하면서 리프 노드(자식의 개수가 0인 노드)라면 count를 증감시켜준다.

 

---

<코드>

node_list[]: index가 노드의 값이며, [index]값은 부모의 값을 담고 있는 리스트 (ex. [1] = 0이면 노드(1)의 부모는 노드(0))

remove_target: 삭제할 노드 key 값

Node:{

append(): left가 비어 있으면 왼쪽 자식에 추가, 아니라면 오른쪽 자식에 추가

remove(): 왼쪽 자식이 삭제하려는 타겟이라면 left=None, 오른쪽 자식이 삭제하려는 타겟이라면 right=None

search(): 전위 순회를 통해 리프 노드가 몇 개 있는지 탐색

}

---

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def append(self, parents, index):
        if self.key == parents:
            if not self.left: # find left child or right child
                self.left = Node(index)
            else:
                self.right = Node(index)
            return

        if self.left:
            self.left.append(parents, index)
        if self.right:
            self.right.append(parents, index)

    def remove(self, target):
        if self.left:
            if self.left.key == target: # 왼쪽 자식이 삭제하려는 Node이면 삭제
                self.left = None
                return
            self.left.remove(target)
        if self.right:
            if self.right.key == target: # 오른쪽 자식이 삭제하려는 Node이면 삭제
                self.right = None
                return
            self.right.remove(target)


    def search(self):
        if not self.left and not self.right: # 리프 노드
            global count
            count += 1

        if self.left:
            self.left.search()
        if self.right:
            self.right.search()

if __name__ == '__main__':
    # input
    N = sys.stdin.readline()
    node_list = list(map(int, sys.stdin.readline().split()))
    remove_target = int(sys.stdin.readline())

    # init
    node = Node(0)
    count = 0

    if remove_target == 0:
        print(0)
    else:
        # create tree
        for i in range(1, len(node_list)):
            if node_list[i] != -1:
                node.append(node_list[i], i)
        # remove node
        node.remove(remove_target)
        # calculate count
        node.search()
        # print
        print(count)