[프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임(Python)

문제

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

프로그래머스

---

풀이

• 이진트리 문제로 별다른 풀이법은 생각나지 않아 노드와 트리를 직접 구현했다.
• 노드의 data로 비교하는 것이 아닌 x, y 값으로 트리를 생성해야한다.
• 깊이가 0부터 순서대로 저장하기 위해 먼저 y를 내림차순으로 정렬한다.
• 노드는 x,  y, data(노드의 번호) 그리고 자식 노드의 대한 값을 저장한다.
• 정렬했던 순서대로(깊이가 0인 노드부터) 노드들을 뽑아내며 x값을 비교해 왼쪽 서브트리인지 오른쪽 서브트리인지 판단해 트리를 생성한다.
• 트리를 생성 후 순회 알고리즘을 작성한다.
• 전위 순회: root - left - right
• 후위 순회: left - right - root

코드

import sys
sys.setrecursionlimit(10**6)

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

class BinaryTree:
    def __init__(self):
        self.root = None
        self.pre_answer = []
        self.post_answer = []
        
    def insert(self, parent, node):
        if parent is None:
            parent = node
            
        if node.x < parent.x:
            parent.left = self.insert(parent.left, node)
        elif node.x > parent.x:
            parent.right = self.insert(parent.right, node)
            
        return parent
        
    def create_tree(self, nodes):        
        for node in nodes:
            self.root = self.insert(self.root, node)
            
    def preorder(self, node):
        self.pre_answer.append(node.data)
        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
    
    def postorder(self, node):
        if node.left:
            self.postorder(node.left)
        if node.right:
            self.postorder(node.right)
        self.post_answer.append(node.data)
        
def solution(nodeinfo):
    nodeinfo = [[coor[0], coor[1], i+1] for i, coor in enumerate(nodeinfo)]
    nodeinfo.sort(key=lambda x: -x[1])
    
    nodes = [Node(x, y, data) for x, y, data in nodeinfo]
    
    tree = BinaryTree()
    tree.create_tree(nodes)
    tree.preorder(tree.root)
    tree.postorder(tree.root)
        
    return [tree.pre_answer, tree.post_answer]