[프로그래머스] 길 찾기 게임

아이디어 도출 방법

1. 주어진 입력에서 트리를 구성하는 방법은?

• 트리는 root node가 하나만 존재함으로 y축이 제일 높은 node가 root일 수 밖에 없다.

 nodeinfo.sort(key=lambda nodeinfo:(-nodeinfo[1], nodeinfo[0]))

• root 노드를 기준으로 x 값이 root보다 작으면 왼쪽, 크다면 오른쪽으로 분리해주면 된다. 

    root_node = nodeinfo.pop(0)
    
    make_tree([node for node in node_list if node[0] < root_node[0]])
    make_tree([node for node in node_list if node[0] > root_node[0]])

증명

y축으로 정렬하면 아래와 같은 그림이 형성되어 질 것이다. 물론 순서는 틀릴 수 있다. 하지만 root 노드의 값보다 작은 값만을 추출한다면 빨간색 네모 박스만 걸리게 될 것이다. x의 순서는 보장할 수 없지만 y의 순서는 보장할 수 있기 때문에 해당 리스트의 첫 번째 값을 루트로 뽑아도 되는 것이다. 

pre_order = []
last_order = []

def make_tree(nodeinfo):
    """현재 노드를 기준으로 하여 이진 트리를 구성한다.

    현재 레밸보다 아래에 있는 노드 중에 x값이 root의 x 값보다 작은 것을 왼쪽으로 큰 부분을 오른쪽으로 보낸다.

    Args:
        nodeinfo (_type_): y 축을 기준으로 정렬된 node
    """
    global pre_order, last_order

    if not nodeinfo:
        return

    root_node = nodeinfo.pop(0)
    node_list = nodeinfo[:]

    pre_order.append(root_node[2])
    
    make_tree([node for node in node_list if node[0] < root_node[0]])
    make_tree([node for node in node_list if node[0] > root_node[0]])

    last_order.append(root_node[2])
    
    return

def solution(nodeinfo):
    """전위 순회와 후위 순회의 결과를 반환한다.

    Args:
        nodeinfo (_type_): 입력으로 주어진 노드

    Returns:
        _list_: 전위 순회와 후위 순회의 결과를 반환한다.
    """
    for idx, node in enumerate(nodeinfo):
        node.append(idx + 1)
    nodeinfo.sort(key=lambda nodeinfo:(-nodeinfo[1], nodeinfo[0]))

    make_tree(nodeinfo)

    return [pre_order, last_order]




if __name__ == "__main__":
    nodeinfo = [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]
    result = [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

    print(solution(nodeinfo))

후기

트리여서 조금 무서웠는데 생각보다 별 거 없었다. 중요한 점은 재귀탐색의 깊이를 조정해야 했는데 이러한 방식 때문에 정답률이 낮았던 것 같다.