[프로그래머스 level3 길 찾기 게임] 이진 트리 및 전위순회, 후위순회 구현하기!

해결해야하는 문제는 다음과 같았다.

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

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

 

우선 이 문제를 해결하기 위해서는 이진트리 및 전위순회 후위순회를 알아야할 것 같았다.

기본 개념은 다음과 같다.

이진트리

각각의 노드가 최 대 두 개의 자식 노드를 가지는 트리 자료 구조이다.

 

이진 탐색 트리

이진 탐색의 효율성을 유지하면서 빈번한 자료의 입력과 삭제가 가능하도록 한ㄷ나.

- 각 노드의 왼쪽 서브트리는 해당 노드 값보다 작은 값을 가진 노드로 이루어져있다.

- 각 노드의 오른쪽 서브트리는 해당 노드 값보다 큰 값을 가진 노드로 이루어져있다.

- 중복되는 노드가 없다.

-> 왼쪽은 현재 값보다 작다, 오른쪽은 현재값보다 크다를 통해 빠르게 search 가 가능하다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

 

preorder (Dfs 같은듯!)

root -> left -> right 순서로 순회한다.

F -> B -> A -> D -> C -> E -> G -> I -> H

 

postorder

left -> right -> root 순서로 순회한다.

A -> C -> E -> D -> B -> H -> I -> G -> F

 

 

cf ) inorder 

left->root -> right 순서로 순회한다.

A -> B -> C -> D -> E -> F -> G -> H -> I

 

 

구현은 다음과 같이 하였다.

 

아이디어를 바탕으로 작성한 코드는 다음과 같다.

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

class BT():
    def __init__(self):
        self.root = None
        self.preorder_arr = []
        self.postorder_arr = []

    def insert(self,idx,x,y):
        if self.root is None :
            self.root = Node(idx,x,y)
            return
        self.current = self.root
        while True :
            if x < self.current.x :
                if self.current.left != None :
                    self.current = self.current.left
                else :
                    self.current.left = Node(idx,x,y)
                    break
            else :
                if self.current.right != None :
                    self.current = self.current.right
                else :
                    self.current.right = Node(idx,x,y)
                    break



    def preorder(self,node):
        if node != None :
            self.preorder_arr.append(node.idx)
            if node.left :
                self.preorder(node.left)
            if node.right :
                self.preorder(node.right)

    def postorder(self,node):
        if node != None :
            if node.left :
                self.postorder(node.left)
            if node.right :
                self.postorder(node.right)
            self.postorder_arr.append(node.idx)

def solution(nodeinfo):
    answer = []
    binary_tree = BT()
    newnodeinfo = []
    for idx, value in enumerate(nodeinfo) :
        newnodeinfo.append([idx+1,value[0], value[1]])
    newnodeinfo.sort(key=lambda x : x[2],reverse=True)
    for idx, tx,ty in newnodeinfo :
        binary_tree.insert(idx,tx, ty)

    binary_tree.preorder(binary_tree.root)
    binary_tree.postorder(binary_tree.root)
    answer.append(binary_tree.preorder_arr)
    answer.append(binary_tree.postorder_arr)

    return answer

하지만 이는 6,7 번 테스트케이스에서 런타임 에러가 난다.

질문하기에 똑같은 고민을 하는 분이 있어, 확인해본 결과

재귀함수 호출 횟수 제한 때문이었다.

이는 다음과 같은 코드를 통해 제한 횟수를 늘려주었다.

import sys
sys.setrecursionlimit(10**6)

 

이를 추가한 최종 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6)


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

class BT():
    def __init__(self):
        self.root = None
        self.preorder_arr = []
        self.postorder_arr = []

    def insert(self,idx,x,y):
        if self.root is None :
            self.root = Node(idx,x,y)
            return
        self.current = self.root
        while True :
            if x < self.current.x :
                if self.current.left != None :
                    self.current = self.current.left
                else :
                    self.current.left = Node(idx,x,y)
                    break
            else :
                if self.current.right != None :
                    self.current = self.current.right
                else :
                    self.current.right = Node(idx,x,y)
                    break



    def preorder(self,node):
        if node != None :
            self.preorder_arr.append(node.idx)
            if node.left :
                self.preorder(node.left)
            if node.right :
                self.preorder(node.right)

    def postorder(self,node):
        if node != None :
            if node.left :
                self.postorder(node.left)
            if node.right :
                self.postorder(node.right)
            self.postorder_arr.append(node.idx)

def solution(nodeinfo):
    answer = []
    binary_tree = BT()
    newnodeinfo = []
    for idx, value in enumerate(nodeinfo) :
        newnodeinfo.append([idx+1,value[0], value[1]])
    newnodeinfo.sort(key=lambda x : x[2],reverse=True)
    for idx, tx,ty in newnodeinfo :
        binary_tree.insert(idx,tx, ty)

    binary_tree.preorder(binary_tree.root)
    binary_tree.postorder(binary_tree.root)
    answer.append(binary_tree.preorder_arr)
    answer.append(binary_tree.postorder_arr)

    return answer