길 찾기 게임

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42892?language=python3

이진 트리를 구현하고 그 안에서 전위 순회와 후위 순회를 다시 구현하는 방식으로 문제를 해결했습니다.

전위 순회는 금방 떠올릴 수 있었는데 후위 순회를 고려하느라 많이 헤맸습니다.

 

 

입력으로 주어지는 node의 최대 깊이가 1000인 것을 고려할 때, 배열로 이진 트리를 구현하는 것은 메모리 낭비가 심할 것으로 생각하고 번호, x값, leftNode, rightNode를 property로 갖는 Node class를 생성했습니다.

 

 

완전 이진 트리가 아니므로 leaf node가 아닌 모든 node가 leftNode와 rightNode를 가질 필요는 없습니다.

 

 

문제의 조건 중 

• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

로부터 이진 트리를 구현할 힌트를 얻을 수 있습니다.

 

추가하려는 node들이 level 내림차순으로 정렬되어있을 때, 추가하는 node의 x값이 탐색 중인 node의 x값보다 작으면 left로, 반대의 경우는 right로 탐색을 진행하며 node를 추가할 수 있습니다.

 

 

모든 노드의 좌표는 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

라고 문제에서 설명하므로 우리는 그러한 경우를 고려하지 않아도 됩니다.

 

 

이진 트리가 구현되어있을 때 전위 순회와 후위 순회를 구현하는 방법에 대해 알아가는 것이 좋습니다.

간단한 로직으로 구현할 수 있습니다.

 

 

문제에서 재귀 함수를 사용하는데 python3으로 제출할 경우 재귀함수 호출 제한으로 인해 런타임 에러가 발생합니다. 반드시 재귀 깊이를 늘려주는 명령을 실행해야 합니다.

 

 

import sys
sys.setrecursionlimit(10000)

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

def addNode(parent:Node, child:Node):
    if parent.x > child.x:
        if parent.left == None:
            parent.left = child
        else:
            addNode(parent.left, child)
    else:
        if parent.right == None:
            parent.right = child
        else:
            addNode(parent.right, child)

def preorder(answer:list, node:Node):
    if node == None:
        return
    answer.append(node.num)
    preorder(answer, node.left)
    preorder(answer, node.right)

def postorder(answer:list, node:Node):
    if node == None:
        return
    postorder(answer, node.left)
    postorder(answer, node.right)
    answer.append(node.num)

def solution(nodeinfo):
    maxLevel, idx_root = nodeinfo[0][1], 0
    for i in range(1, len(nodeinfo)):
        if maxLevel < nodeinfo[i][1]:
            maxLevel = nodeinfo[i][1]
            idx_root = i

    root = Node(idx_root+1, nodeinfo[idx_root][0])
    temp = []
    for i in range(len(nodeinfo)):
        temp.append((nodeinfo[i][0], nodeinfo[i][1], i+1))
    temp.sort(key = lambda x:-x[1])
    for i in range(1, len(temp)):
        addNode(root, Node(temp[i][2], temp[i][0]))
    
    list_preorder = []
    preorder(list_preorder, root)
    list_postorder = []
    postorder(list_postorder, root)

    return [list_preorder, list_postorder]