[programmers/py] 길 찾기 게임

길 찾기 게임

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

문제 설명

이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

풀이

전위, 후위 탐색 문제다.

1. x 좌표를 기준으로 오름차순 정렬을한다.
2. y값이 가장 큰 노드를 찾는다.
3. answer에 노드를 추가
   3-1 전위는 부모->왼쪽->오른쪽이라 먼저 추가
   3-2 후위는 왼쪽->오른쪽->부모 순서라 마지막에 추가
4. left, right로 구분해서 가장 높은 y값이 부모의 자식 노드들

from sys import setrecursionlimit
setrecursionlimit(10000)

def solution(nodeinfo):
    answer = [[], []]
    # i+1은 노드 번호
    nodeinfo = sorted( [(x,y,i+1) for i,(x,y) in enumerate(nodeinfo)] , key=lambda x:x[0])

    def Rec(nodeinfo):
        if nodeinfo:
            h = (0, -1, 0)
            for idx, (x, y, i) in enumerate(nodeinfo):
                if y > h[1]:
                    h = (idx, y, i)
            answer[0].append(h[-1])
            left, right = nodeinfo[:h[0]], nodeinfo[h[0]+1: ]
            Rec(left)
            Rec(right)
            answer[1].append(h[-1])
    
    Rec(nodeinfo)
    
    return answer