[프로그래머스] - 길 찾기 게임 (파이썬)

import sys
sys.setrecursionlimit(10**3)


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


class Tree:
    def __init__(self, index, x, y):
        self.head = Node(index, x, y)

    def insert(self, index, x, y):
        curr = self.head
        while True:
            if curr.x > x:
                if curr.left == None:
                    curr.left = Node(index, x, y)
                    break
                else:
                    curr = curr.left
            else:
                if curr.right == None:
                    curr.right = Node(index, x, y)
                    break
                else:
                    curr = curr.right

    def pre(self):
        result = []

        def do(curr):
            result.append(curr.index)
            if curr.left != None:
                do(curr.left)
            if curr.right != None:
                do(curr.right)
        do(self.head)
        return result

    def post(self):
        result = []

        def do(curr):
            if curr.left != None:
                do(curr.left)
            if curr.right != None:
                do(curr.right)
            result.append(curr.index)
        do(self.head)
        return result


def solution(nodeinfo):
    nodes = [[i+1, nodeinfo[i]] for i in range(len(nodeinfo))]
    nodes.sort(key=lambda x: [-x[1][1], x[1][0]])
    tree = Tree(nodes[0][0], nodes[0][1][0], nodes[0][1][1])
    for node in nodes[1:]:
        tree.insert(node[0], node[1][0], node[1][1])

    pre = tree.pre()
    post = tree.post()

    answer = [pre, post]
    return answer

 

2019 카카오 블라인드 - 5번

Node : index(해당 노드의 인덱스값), x(좌표), y(좌표), left(왼쪽자식), right(오른쪽자식)

Tree : 생성시 Node생성, insert(노드 추가), pre(전위순회), post(후위순회)

1. nodes를 nodeinfo의 인덱스와 좌표를 넣은 값으로 초기화

2. y좌표가 큰 순서, x좌표가 작은 순서로 정렬

3. 가장 초기값(최상위 노드)인 Tree클래스로 tree 정의

4. 초기 노드를 제외한 나머지를 tree에 insert해주면서 트리 만들기

    - x 좌표가 작으면 왼쪽노드 크면 오른쪽노드

5. 전위 순회와 후위 순회 실시 (result 리스트 반환)

    - 선방문

    - 후방문

6. answer 출력