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

문제는 여기!

문제에서 주어진 좌표들을 트리로 표현헤야 힌다. 그 다음, 구현한 트리를 바탕으로 어떻게 순회를 구현할지가 핵심인 문제였다.

제한사항 및 주의사항

모든 노드의 x좌표는 서로 다르며, y좌표가 같으면 같은 레벨로 간주한다.

자식 노드의 y값은 항상 부모의 y값보다 작으며, 임의의 노드 V에서 왼쪽 서브트리의 x값은 V의 x보다 작다. 반대로 오른쪽 서브트리의 x값은 V의 x보다 크다.

풀이전략

우선 주어진 nodeinfo를 순서에 맞게 번호로 표현해야 한다. 시간 효율을 위해 나는 딕셔너리를 선언했다.

ex) (x, y) : 1, (x, y) : 2

참고로 딕셔너리의 키는 리스트가 올 수 없어서 튜플로 처리했다.

이제 nodeinfo를 y에 대해 내림차순, x에 대해 오름차순으로 정렬하자. 그 이유는 트리구조에서 y값이 제일 큰 것이 최상단 부모일테고, 같은 y값이면 x가 작은 것부터 차례대로 왼쪽 서브트리, 오른쪽 서브트리에 값을 넣을 수 있기 때문이다.

for를 통해 정렬된 nodeinfo의 node들을 하나씩 트리에 넣자. 이 때, 나는 트리를 표현하기 위해 클래스를 선언하여 data(현재 트리의 좌표), left(현재 트리의 왼쪽 서브트리), right(현재 트리의 오른쪽 서브트리)를 변수로 표현했다.

해당 노드들을 알맞은 서브트리에 넣는 방법은 최상단 노드를 변수에 넣고, y값을 비교한다. y값이 작은 경우는 자식이기 때문에 최상단 노드의 x값을 비교해서 왼쪽, 오른쪽에 넣을지 판단하자. 최상단 노드의 왼쪽, 오른쪽이 만약 값이 있을 경우에는 최상단 노드를 넣은 변수에 해당 왼쪽이나 오른쪽에 값을 집어넣고 while문을 이용해 왼쪽이나 오른쪽이 비었을 경우를 찾고 트리에 값을 넣을 때 까지 돌린다. 자세한 것은 코드를 보면 아마 이해가 될 것이다.

그 다음은 전위순회, 후위순회 결과를 담을 리스트를 선언하였다. 리턴 시에는 [전위순회 결과 리스트, 후위순회 결과 리스트] 로 리턴하자. 탐방 시에는 앞에서 선언한 딕셔너리를 활용해 해당 노드에 맞는 번호를 찾아서 결과 리스트에 대입한다.

전위 순회 : 순회할 때, 현재 탐방중인 노드를 먼저 리스트에 넣고 왼쪽을 우선으로 순회한다. 왼쪽을 순회할 수 없다면 오른쪽, 그 마저도 없으면 위로 올라가서 탐방하지 않은 노드들을 항상 왼쪽을 우선으로 탐색한다.

후위 순회 : 순회할 때, 왼쪽을 우선으로 순회한다. 왼쪽 서브트리가 없다면 오른쪽을 탐방하고 더 이상 서브트리가 없을 때 리스트에 노드의 값을 집어 넣는 방식이다. 그림을 통해 이해해보자! 트리 구조는 문제에서 사용된 예제를 활용하겠다!

좌표는 생략했다. 이 상태에서 어떤 순회를 하든 항상 최상단 노드를 먼저 방문한다. 이 때, 전위 순회의 경우에는 방문중인 노드를 탐색하는 것이 먼저가 아니라 리스트에 방문중인 노드 정보를 삽입한다.

이러한 방식으로 전위 순회를 하면 7, 4, 6, 9, 1, 8, 5, 2, 3 이 나온다. 후위순회의 그림은 다음과 같다.

이렇게 후위 순회를 하면 9, 6, 5, 8, 1, 4, 3, 2, 7이 나온다. 이제 코드를 보자.

import sys
sys.setrecursionlimit(10**6)


class Tree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def preorder(tree, node_index, preorder_list):
    preorder_list.append(node_index[tuple(tree.data)])
    if tree.left:
        preorder(tree.left, node_index, preorder_list)
    if tree.right:
        preorder(tree.right, node_index, preorder_list)


def postorder(tree, node_index, postorder_list):
    if tree.left:
        postorder(tree.left, node_index, postorder_list)
    if tree.right:
        postorder(tree.right, node_index, postorder_list)
    postorder_list.append(node_index[tuple(tree.data)])


def solution(nodeinfo):
    node_index = {tuple(nodeinfo[i]): i + 1 for i in range(len(nodeinfo))}
    nodeinfo = sorted(nodeinfo, key=lambda x: (-x[1], x[0]))

    tree = None
    for node in nodeinfo:
        if tree is None:
            tree = Tree(node)
        else:
            point = tree
            while True:
                if point.data[1] > node[1] and point.data[0] > node[0]:
                    if point.left is None:
                        point.left = Tree(node)
                        break
                    else:
                        point = point.left
                elif point.data[1] > node[1] and point.data[0] < node[0]:
                    if point.right is None:
                        point.right = Tree(node)
                        break
                    else:
                        point = point.right
    preorder_list = []
    postorder_list = []
    preorder(tree, node_index, preorder_list)
    postorder(tree, node_index, postorder_list)
    return [preorder_list, postorder_list]