[프로그래머스(파이썬/Python)] 길 찾기 게임(2019 카카오 블라인드)

https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

 

이 문제의 핵심은 (x, y) 형태로 주어진 점들을 어떻게 이진트리 형태로 만들 것인가였다고 생각합니다. 이진 트리를 만들기만 하면 순회같은 경우에는 재귀 함수를 이용해 쉽게 구현할 수 있기 때문이죠.

 

제가 이진 트리를 만들기 위해 수행했던 로직을 간단히 정리하면 아래와 같습니다.

 

1) 우선 주어진 (x, y) 점들에 대한 키값으로 인덱스 번호를 붙여서 딕셔너리 형태로 만들어줍니다.

 

2) 그리고 딕셔너리의 value값인 (x, y)으로 정렬을 수행해서 위쪽부터 왼쪽, 오른쪽을 거치면서 내려오는 트리 형태로 만들어줍니다. 여기까지 만든 딕셔너리 형태는 아래와 같겠죠.

ex) // nodeDict = {7: [8, 6], 4: [3, 5], 2: [11, 5], 6: [1, 3], 1: [5, 3], 3: [13, 3], 9: [2, 2], 8: [7, 2], 5: [6, 1]}

 

3) 이제 root 바로 아래 자식노드들을 방문하면서 트리의 적절한 위치에 삽입을 해줍니다.

맨 위 root 노드부터 시작하여 x 값을 비교해서 작으면 왼쪽, 크면 오른쪽으로 이동하고, 그 자리에 아직 노드가 없다면(-1이라면) 그 위치에 넣어주면 됩니다. 이미 자식 노드가 그 자식 노드부터 다시 아래로 뻗어나가는 과정을 반복하면 됩니다.

 

1~3 과정을 통해 tree가 생성되었고, 해당 트리를 가지고 전위순회와 후위순회를 한 결과값을 리턴해주면 됩니다.

 

 

[풀이]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)


def preOrder(tree, root, route):
    route.append(root)

    left, right = tree[root][0], tree[root][1]
    if left != -1:
        preOrder(tree, left, route)
    if right != -1:
        preOrder(tree,right, route)

    return route

def postOrder(tree, root, route):
    left, right = tree[root][0], tree[root][1]
    if left != -1:
        postOrder(tree, left, route)
    if right != -1:
        postOrder(tree,right, route)
    route.append(root)

    return route

def makeTree(tree, nodeDict, root, node):
    x, y = nodeDict[node][0], nodeDict[node][1]

    while True:
        rootX, rootY = nodeDict[root][0], nodeDict[root][1]
        # 왼쪽 서브트리에 삽입
        if rootX > x:
            if tree[root][0] == -1:
                tree[root][0] = node
                break
            else:
                root = tree[root][0]

        # 오른쪽 서브트리에 삽입
        else:
            if tree[root][1] == -1:
                tree[root][1] = node
                break
            else:
                root = tree[root][1]
            

def solution(nodeinfo):
    answer = [[],[]]
    nodeList = defaultdict(list)
    for idx, node in enumerate(nodeinfo):
        nodeList[idx+1] = node

    # Root부터 왼쪽, 오른쪽 순서로 내려오는 노드 형태로 정렬
    nodeList = sorted(nodeList.items(), key = lambda x: (-x[1][1], x[1][0]))
    root = nodeList[0][0]
    nodeDict = dict(nodeList)


    # 트리의 왼쪽, 오른쪽 자식 노드의 인덱스를 -1로 초기화
    tree = defaultdict(list)
    for i in range(1, len(nodeinfo)+1):
        tree[i] = [-1,-1]

    for i in range(1, len(tree)):
        makeTree(tree, nodeDict, root, nodeList[i][0])

    # 순회 경로를 위한 빈 리스트를 매개변수로 초기화하고 함수 콜
    answer[0] = preOrder(tree, root, [])
    answer[1] = postOrder(tree, root, [])

    return answer