백준 문제 풀이 - 트리 1068번

📜 문제 이해하기

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
리프 노드의 갯수를 구하여라

💡 문제 재정의

주어진 입력으로 트리를 구성하고 한 노드를 지웠을 때 남은 leaf 노드들의 갯수를 출력

✏️ 계획 수립

이 문제를 처음 봤을 때 예시가 이진 트리여서 이진 트리로 문제를 풀면 안된다. 노드는 자식 노드들이 2개 이상일 수도 있다고 생각하고 풀어야 한다.
1) 노드 클래스 만들기
2) 트리 클래스 만들기
3) 트리에 값 집어넣기
4) 트리에서 특정 값 지우기
5) 남은 leaf 노드 출력하기

💻 계획 수행

import sys


class Node:
    def __init__(self, _data, _parent=None):
        self.data = _data
        self.parent = _parent
        self.child = []


class Tree:
    def __init__(self):
        self.root = None
        self.count = 0

    def insert(self, _node):
        _node.parent.child.append(_node)

    def delete(self, _node):
        for child in _node.parent.child:
            if child == _node:
                _node.parent.child.remove(_node)

    def find_leaf(self, _node):
        if _node.child:
            for child in _node.child:
                self.find_leaf(child)
        else:
            self.count += 1


if __name__ == '__main__':
    N = int(sys.stdin.readline())
    input_data = list(map(int, sys.stdin.readline().split()))
    node_list = [Node(data) for data in range(N)]

    tree = Tree()

    for data, parent in enumerate(input_data):
        if parent == -1:
            node_list[data].parent = parent
            tree.root = node_list[data]
        else:
            node_list[data].parent = node_list[parent]
            tree.insert(node_list[data])

    delete_data = int(input())
    if node_list[delete_data].parent == -1:
        print(0)
    else:
        tree.delete(node_list[delete_data])
        tree.find_leaf(tree.root)
        print(tree.count)

🤔 회고

트리 자료구조를 만들 수 있으면 쉽게 풀 수 있는 문제였다. 다만 이진트리인줄 알고 시간을 많이 사용했다. 문제를 꼼꼼히 읽고 정확히 파악하기 위해 노력해야겠다.