[Programmers] 길 찾기 게임 문제 풀이 (Python)

1. 문제 풀이

주어진 노드를 이진트리로 구성해 전위 순회, 후위 순회 방식으로 순회한 결과를 구하는 문제이다.

이진트리(Binary Tree) 구성하기

이진 트리는 트리 중 비교적 구현이 쉽다.

• 각 level별로 노드의 최대 갯수가 정해져있다. e.g.) level1: 1개, level2: $2^2$개, … , level n: $2^n$개
• 트리의 depth를 안다면 최대 노드 갯수도 정해진 것이므로 array(list)를 이용해 비교적 쉽게 구현할 수 있다

이진 트리를 array(list)를 이용해 구성을 한다고 가정해보자.

• root의 index: 1
• 현재 부모노드의 index를 i라고 한다면
  • 왼쪽 자식 노드의 index: 2 * i
  • 오른쪽 자식 노드의 index: (2 * i) + 1

array(list)를 이용해 이진 트리를 구성할 때 주의할 점은 트리의 depth를 이용해 먼저 트리 array를 만들기 때문에 트리 array의 length를 벗어나지 않도록 주의해야한다.(index error)

dictionary를 사용하면 depth를 따로 구할 필요 없고 공간을 절약할 수 있기 때문에 본 문제는 dictionary를 이용해 풀었다.

순회

• 전위 순회(preorder traversal): 현재 노드 방문 → 왼쪽 서브트리 전위 순회 → 오른쪽 서브트리 전위 순회
• 후위 순회(postorder traversal): 왼쪽 서브트리 후위 순회 → 오른쪽 서브트리 후위 순회 → 현재 노드 방문

트리를 순회하는 방법은 전위 순회, 후위 순회 말고도 여러가지가 있기 때문에 wikipedia를 참고하면 좋을 것 같다.

코드 구현시 주의할 점

• Python을 이용해 재귀함수를 구현할 때는 recursion error가 발생하지 않도록 주의해야한다.
• Python에서 default로 설정된 maximum recursion depth는 1000이기 때문에 재귀 호출이 1000번을 넘는다면 Recursion Error가 발생한다. sys.setrecursionlimit(number) 을 이용해 maximum recursion depth를 늘릴 수 있다.

2. 코드

import sys
sys.setrecursionlimit(1000000)

node = {}
pre = []
post = []

def make_tree(tree,now,idx):
    if now not in tree:
        tree[now] = idx
        return
    if node[tree[now]][0] > node[idx][0]:
        make_tree(tree,2*now,idx)
    else:
        make_tree(tree,2*now+1,idx)

def pre_order(tree, idx):
    if idx not in tree: return
    pre.append(tree[idx])
    pre_order(tree, 2*idx)
    pre_order(tree, 2*idx+1)

def post_order(tree, idx):
    if idx not in tree: return
    post_order(tree, 2*idx)
    post_order(tree, 2*idx+1)
    post.append(tree[idx])

def solution(nodeinfo):
    nodes = []

    for i,(x,y) in enumerate(nodeinfo):
        node[i+1] = (x,y)
        nodes.append((i+1,x,y))
    nodes.sort(key = lambda x: (-x[2], x[1]))

    tree = {}
    for idx, _,_ in nodes:
        make_tree(tree,1,idx)

    pre_order(tree, 1)
    post_order(tree, 1)

    return [pre,post]