[ Lv 3 ] 길 찾기 게임

풀이 과정

1. 트리를 만들어주어야 하는 문제이므로 트리를 구성할 노드 class 정의
2. 모든 노드에 인덱스 달아준 다음, 모든 노드의 좌표를 y 좌표 기준 내림차순으로 정렬
3. 가장 y좌표가 큰 케이스를 루트 노드로 지정
4. 이제 y좌표 순으로 트리에 삽입
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 작다면 왼쪽 이동
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 크다면 오른쪽 이동
   • 이동 하다가 현재 노드의 left/right가 None이라면 삽입
5. 전위순회 / 후위순회를 recursion으로 구현

트리 만드는거 연습이 필요함.. 어렵게 구현

---

소스 코드

import sys

sys.setrecursionlimit(10**6)

class tree:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element

def tree_push(root, node):
    # X좌표 비교
    if root == None:
        root = node

    if root.element[0] > node.element[0]:
        if root.left == None:
            root.left = node
        else:
            tree_push(root.left, node)

    elif root.element[0] < node.element[0]:
        if root.right == None:
            root.right = node
        else:
            tree_push(root.right, node)

def preorder(node, answer):
    if node == None:
        return
    answer.append(node.element[2])
    preorder(node.left, answer)
    preorder(node.right, answer)

def postorder(node, answer):
    if node == None:
        return
    postorder(node.left, answer)
    postorder(node.right, answer)
    answer.append(node.element[2])


def solution(nodeinfo):
    answer = [[], []]
    for idx, node in enumerate(nodeinfo):
        node.append(idx+1)
    nodeinfo.sort(key=lambda x:(-x[1], x[0]))

    root = tree(nodeinfo[0])
    for i in range(1, len(nodeinfo)):
        temp = tree(nodeinfo[i])
        tree_push(root, temp)

    preorder(root, answer[0])
    postorder(root, answer[1])
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges