[프로그래머스] 길 찾기 게임 (Python)

https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

 

 

트리 구조는 학부 자료구조 시간 때 어느 정도 했다고 생각했는데

막상 직접 구현하려니까 도저히 떠오르질 않았다...

 

다른 분들 풀이를 참고했다 - 나중에 추가로 공부를 더 해야겠다.

import sys
sys.setrecursionlimit(10**5)
class Tree:
    def __init__(self, nodeinfo):
        self.idx, *self.root = nodeinfo.pop()
        leftTree = list(filter(lambda x: x[1] < self.root[0], nodeinfo))
        rightTree = list(filter(lambda x: x[1] > self.root[0], nodeinfo))
        self.left = Tree(leftTree) if leftTree else False
        self.right = Tree(rightTree) if rightTree else False


def recursiveTraversal(tree, preorder, postorder):
    preorder.append(tree.idx)
    if tree.left:
        recursiveTraversal(tree.left, preorder, postorder)
    if tree.right:
        recursiveTraversal(tree.right, preorder, postorder)
    postorder.append(tree.idx)


def solution(nodeinfo):
    nodeinfo = [(i+1, x, y) for i, (x, y) in enumerate(nodeinfo)]
    nodeinfo = sorted(nodeinfo, key=lambda x: x[2])
    tree = Tree(nodeinfo)
    preorder, postorder = [], []
    recursiveTraversal(tree, preorder, postorder)
    return [preorder, postorder]