길 찾기 게임 [2019 KAKAO BLIND RECRUITMENT]

1) 문제 접근 방법

- 이 문제는 이진 탐색 트리의 정의를 정확하게 이해하는 것이 중요한 문제이다. 

  문제의 요구 사항에 따라, binaryTree를 탐색하면서, 현재 루트 값보다 작으면, 왼쪽으로, 

  현재 루트 값보다 크면 오른쪽으로 탐색하면서, 빈 위치에 값을 넣어준다. 

 

- 이를 위해서는 class Node라는 것이 선언되어야 하고, 이것을 만드는 __init__ 함수 또한 명확히 정의해야 한다. 

 

- 중요한 것은 이진 탐색 트리를 만들 때, y값이 큰 순으로 순차적으로 하나씩 만들어줘야 한다는 것이다.

-> 왜냐하면 y값이 클 수록 이진 탐색 트리의 더 높은 위치에 존재하기 때문이다. 

-> 이를 위해서는 저장된 노드값들을 y값을 기준으로 내림차순 정렬을 해야 한다. 

 

- 그 다음 preOrder와 postOrder는 일반적인 전위 탐색, 후위 탐색의 정의에 따라서 구현하면 된다. 

 

- 또한 이 문제는 DFS를 적용했는데, 노드가 최대 10000개 까지 있을 수 있다.

-> 그런데 파이썬에서 DFS는 depth가 1000이므로, 이 경우는 setrecursionlimit을 통해 

    재귀의 제한수를 바꿔줘야 한다. 

 

 

 

2) 내 코드

from sys import setrecursionlimit
setrecursionlimit(10000)

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

        
root = None

def binaryTree(root, x, y, num):
    
    if x < root.x:
        if root.left == None:
            root.left = Node(x, y, num)
            return 
        else:
            binaryTree(root.left, x, y, num)
        
        
    elif x > root.x:
        if root.right == None:
            root.right = Node(x, y, num)
            return 
        else:
            binaryTree(root.right, x, y, num)
            
def preOrder(root, tmp):
    
    tmp.append(root.num)
    
    if root.left != None:
        preOrder(root.left, tmp)
    
    if root.right != None:
        preOrder(root.right, tmp)
        

def postOrder(root, tmp):
    
    
    if root.left != None:
        postOrder(root.left, tmp)
        
    if root.right != None:
        postOrder(root.right, tmp)
        
    tmp.append(root.num)
    
        
        
def solution(nodeinfo):
    answer = []
    root = None

    nodes = [] 

    for i in range(len(nodeinfo)):
        nodes.append((nodeinfo[i][0], nodeinfo[i][1], i+1))
    
    nodes.sort(key=lambda x:(-x[1], x[0]))
    
    for i in range(len(nodes)): 
    
        x, y, num = nodes[i][0], nodes[i][1], nodes[i][2] 
    
        if i == 0:
            root = Node(x, y, num)
        
        else:
            binaryTree(root, x, y, num)
    
    tmp1 = [] 
    preOrder(root, tmp1)
    answer.append(tmp1)
    tmp2 = [] 
    postOrder(root, tmp2)
    answer.append(tmp2)
    
    return answer