길 찾기 게임

BTS (binary tree search) 를 구현하는 문제입니다.

BTS의 insert, 전위 순회, 후위 순회를 구현하는 문제입니다.

각 노드의 번호를 알기위해 enumerate를 사용하고

y축으로 각 노드를 정렬한다.

def solution(nodeInfo) :
    sorted_node_info = []                           # 트리의 노드를 높이 순으로 정렬하기 위해서
    for idx,[x,y] in enumerate(nodeInfo,1):         # 정렬과 함께 현재 노드의 번호를 확인하기 위해
        sorted_node_info.append([idx,x,y])          # 노드 번호에 따라 값 저장
    sorted_node_info.sort(key = lambda x : x[2])    # y축 값에 따른 정렬
    root_idx,root_x,root_y = sorted_node_info.pop() # 루트노드 값 가져오기
    tree = dict()                                   # 탐색을 위한 트리 생성
    tree[root_idx] = [(root_x,root_y),0,0]

 

 

 

트리에 노드를 추가하는 인설트 함수 생성

입력받은 부모 노드의_idx 값으로 부모 노드의 x,y의 값과 자식 노드의 idx를 가져온다.

자식노드의 idx,x,y의 값을 가져온다.

이후 부모노드의 x축과 자식 노드의 x축을 비교하여 부모 노드의 x축보다 자식노드가 클 경우

자식은 부모의 우측에 있다는 것이고 그 값이 0이면 아직 탐색되지 않았다는 것입니다.

def insert(tree,node,parent_idx):
    (p_x,p_y),left,right = tree[parent_idx]
    idx,x,y = node
    if p_x < x :
        if right != 0 :
            insert(tree,node,right)
        else :
            tree[parent_idx][R] = idx
            tree[idx] = [(x,y),0,0]
    else :
        if left != 0 :
            insert(tree,node,left)
        else:
            tree[parent_idx][L] = idx
            tree[idx] = [(x,y),0,0]

 

이후 완성된 코드

import sys
sys.setrecursionlimit(10**7)
L,R = 1,2
def insert(tree,node,parent_idx):
    (p_x,p_y),left,right = tree[parent_idx]
    idx,x,y = node
    if p_x < x :
        if right != 0 :
            insert(tree,node,right)
        else :
            tree[parent_idx][R] = idx
            tree[idx] = [(x,y),0,0]
    else :
        if left != 0 :
            insert(tree,node,left)
        else:
            tree[parent_idx][L] = idx
            tree[idx] = [(x,y),0,0]

def pre_order(tree,node_idx) :
    path = []
    if node_idx == 0 :
        return path
    
    path.append(node_idx)
    path += pre_order(tree, tree[node_idx][L])
    path += pre_order(tree, tree[node_idx][R])

    return path

def post_order(tree,node_idx) :
    path = []
    if node_idx == 0 :
        return path
    
    path += post_order(tree, tree[node_idx][L])
    path += post_order(tree, tree[node_idx][R])
    path.append(node_idx)

    return path


def solution(nodeInfo) :
    sorted_node_info = []                           # 트리의 노드를 높이 순으로 정렬하기 위해서
    for idx,[x,y] in enumerate(nodeInfo,1):         # 정렬과 함께 현재 노드의 번호를 확인하기 위해
        sorted_node_info.append([idx,x,y])          # 노드 번호에 따라 값 저장
    sorted_node_info.sort(key = lambda x : x[2])    # y축 값에 따른 정렬
    root_idx,root_x,root_y = sorted_node_info.pop() # 루트노드 값 가져오기
    tree = dict()                                   # 탐색을 위한 트리 생성
    tree[root_idx] = [(root_x,root_y),0,0]          # 루트노드 값을 트리에 추가하고 좌측 우측 노드를 확인하기 위한 값 추가

    while sorted_node_info:                         # 정렬된 노드를 하나씩 확인하며 반복문 실행
        node = sorted_node_info.pop()
        insert(tree,node,root_idx)
    
    answer = [pre_order(tree,root_idx),post_order(tree,root_idx)]
    print(a)
    return answer