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

접근

이진트리를 전위 또는 후위순회 하는것은 간단하나,
문제의 입력은 노드의 부모자식 관계를 직접적으로 표현하지 않으므로,
각 노드의 자식노드를 판단할 수 있는 방법이 필요하다.

문제에서 준 예시를 보자

문제의 조건에따라,
7번 노드의 왼쪽 서브트리를 구성하는 모든 노드들의 x좌표값은 모두 7번 노드보다 작다.

또한 4번 노드의 오른쪽 서브트리를 구성하는 모든 노드들은,
4번 노드보다 큰 x좌표값을 가질것이다.

이런식으로 5번노드까지 탐색한다면, 다음과 같은 상태일것이다.

이 과정에서 알 수 있는것은
현재 노드를 중심으로,
왼쪽 서브트리를 탐색할 때는 왼쪽으로,
오른쪽 서브트리를 탐색할 때는 오른쪽으로, 자식 노드가 존재할 수 있는 범위가 감소한다는 것이다.

다시말해,
현재 노드 이하의 레벨에 존재하는 노드 중
위와 같은 범위안에 존재하는 노드들만
현재 노드의 자식 노드이다.

따라서,

부모노드 p의 왼쪽자식노드 l, 오른쪽자식노드 r의 x좌표 범위는
다음과 같이 정의할 수 있다.

p의 왼쪽 경계 $<$ l의 x좌표 $<$ p의 x좌표
p의 x좌표 $<$ r의 x좌표 $<$ p의 오른쪽 경계

또한, 루트 노드의 x좌표 범위는 다음과 같다.

$-\infin <$ 루트노드의 x좌표 $< \infin$ 이다.

---

코드

from collections import defaultdict
import sys
sys.setrecursionlimit(1005)
MAX = 100001
MIN = -1
TREE_DEPTH = 0

def solution(nodeinfo):
    global TREE_DEPTH

    pre_tree = defaultdict(list)
    post_tree = defaultdict(list)
    level = set()

    for i in range(len(nodeinfo)):
        x, y = nodeinfo[i]
        pre_tree[y].append((x, i+1))
        post_tree[y].append((x, i+1))
        level.add(y)

    for i in level:
        pre_tree[i].sort(reverse=True)
        post_tree[i].sort(reverse=True)

    level = sorted(list(level), reverse=True)
    TREE_DEPTH = len(level)
    
    preorder = []
    pre_order(MIN, MAX, 0, preorder, pre_tree, level)
    postorder = []
    post_order(MIN, MAX, 0, postorder, post_tree, level)

    return [preorder, postorder]


def pre_order(left, right, depth, result, tree, level):
    if depth == TREE_DEPTH:
        return
    if len(tree[level[depth]]) <= 0:
        return
    if not (left < tree[level[depth]][-1][0] < right):
        return
    
    x, index = tree[level[depth]].pop()
    result.append(index)
    pre_order(left, x, depth+1, result, tree, level)
    pre_order(x, right, depth+1, result, tree, level)


def post_order(left, right, depth, result, tree, level):
    if depth == TREE_DEPTH:
        return
    if len(tree[level[depth]]) <= 0:
        return
    if not (left < tree[level[depth]][-1][0] < right):
        return
    
    x, index = tree[level[depth]].pop()
    post_order(left, x, depth+1, result, tree, level)
    post_order(x, right, depth+1, result, tree, level)
    result.append(index)

1. level

트리를 루트노드부터 깊은 노드 순으로 탐색하기 위해 level이라는 이름의 set 타입 변수를 선언한 뒤

모든 노드의 y좌표를 저장하고

내림차순으로 정렬된 리스트로 만들어주었다.

2. pre_tree, post_tree

y좌표에 따라 노드의 레벨이 달라지므로
y좌표를 기준으로 노드의 x좌표와 번호를 리스트로 저장하였고,
왼쪽부터 탐색이 진행되기 때문에
각 노드를 x좌표를 기준으로 오름차순 정렬하였다.
또한 각 순회에서 pop() 을 하며 현재 노드를 제거할 것이기 때문에
전위 순회와 후위 순회를 위한 tree를 각각 만들어주었다.

3. order()

인자로 좌, 우 경계값인 left, right를 받는다.
현재 노드가 범위 내에 있는 경우만
이전 재귀 호출을 한 노드의 자식 노드이기 때문에
만약 현재 노드가 좌, 우 경계 밖에 있다면 순회하지 않고 return한다.