[알고리즘] 길 찾기 게임

포인트

• 전위, 후위 그리고 node 구성을 알 수 있는가? 입니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

import sys

sys.setrecursionlimit(10 ** 6)


class Node:
    def __init__(self, id, x, y):
        self.id = id
        self.x = x
        self.y = y
        self.left = None
        self.right = None

    def __str__(self):
        # 클래스를 표현 할때, 사용
        return "Node {} {} {} {} {}".format(self.id, self.x, self.y, self.left.id, self.right.id)


def preorder(pre: list, node: Node) -> None:
    # 재귀적으로 전위 순회를 하는 방법
    if node is not None:
        pre.append(node.id)
        preorder(pre, node.left)
        preorder(pre, node.right)


def postorder(post: list, node: Node) -> None:
    if node is not None:
        # 재귀적으로 후위 순회를 하는 방법
        postorder(post, node.left)
        postorder(post, node.right)
        post.append(node.id)


def add(root: Node, node: Node) -> None:
    # 부모 노드와 자식 노드의 관계
    # 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
    # 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
    if root.x > node.x:
        if root.left is None:
            root.left = node
        else:
            add(root.left, node)
    else:
        if root.right is None:
            root.right = node
        else:
            add(root.right, node)


def solution(nodeinfo: list) -> list:
    nodes = []
    for x, y in nodeinfo:
        nodes.append(Node(len(nodes) + 1, x, y))
    nodes.sort(key=lambda node: (-node.y, node.x))

    root = nodes[0]
    for node in nodes[1:]:
        add(root, node)

    pre, post = [], []
    preorder(pre, root)
    # 재귀적인 전위 순회
    postorder(post, root)
    # 재귀적인 후위 순회
    # 각각의 리스트는 id를 저장한다

    return [pre, post]