프로그래머스 파이썬 길 찾기 게임

 

프로그래머스

 

 

>> 조건에서 노드가 최대 만개이므로 편향이진트리인 경우 재귀가 만번 돌게 되어서 파이썬 기본 재귀 횟수인 1000개를 넘어선다. 그래서 setrecursionlimit으로 재귀횟수를 만번으로 늘려줘야한다.

 

>> 최종적으로 노드의 인덱스를 순서대로 출력해야하므로 초반에 노드의 인덱스를 값에 추가해줘야한다.'

 

>> 주어진 노드들을 조건에 맞게 (y는 큰 값부터, x는 작은 값부터) 정렬하고 나머지는 그냥 이진트리 생성 후 전위순회 후위순회하면 된다.

 

from sys import setrecursionlimit
setrecursionlimit(10000)

#노드 클래스 정의
class Node(object):
    def __init__(self, info):
        self.num = info[2]  #각 노드의 초반 순서 (최종 출력에 쓰인다)
        self.pos = info[:2]  #노드의 x,y좌표
        self.left = None     #노드의 양쪽 값 초기화
        self.right = None

#nodeinfo를 입력받아서 전위순회,후위순회한 인덱스를 반환하는 함수
def solution(nodeinfo):
    for idx in range(len(nodeinfo)):  #초반 인덱스를 각 노드에 세번째 값으로 추가해준다.
        nodeinfo[idx].append(idx+1)
    
    nodeinfo.sort(key=lambda x: (-x[1], x[0]))  #y값이 큰 값부터 작아지도록, x는 작은 값부터 커지도록 정렬
    tree = Node(nodeinfo[0])  #root노드 삽입
    
    for info in nodeinfo[1:]:  #nodeinfo의 두번째 값부터 tree에 add_node함수로 삽입해준다.
        add_node(tree, info)
    
    return [pre_order(tree), post_order(tree)]

#전위탐색
def pre_order(curr):
    path =[curr.num]  #현재노드 일단 저장
    if curr.left:   #왼쪽부터 값 있는지 재귀적으로 확인
        path += pre_order(curr.left)
    if curr.right:   
        path += pre_order(curr.right)
    return path

#후위탐색
def post_order(curr):
    path =[]   #빈 배열 생성
    if curr.left:    #왼쪽부터 재귀적으로 확인
        path += post_order(curr.left)
    if curr.right:
        path += post_order(curr.right)
    path.append(curr.num)  #가장 나중값부터 추가
    return path
        
#트리에 노드 추가하는 함수
def add_node(parent,info):
    if parent.pos[0] > info[0]: #x값이 부모값보다 작으면 부모노드의 왼쪽으로
        if parent.left:     #근데 이제 왼쪽에 값이 이미 있다면,, 재귀적으로 다시 add_node함수 호출
            add_node(parent.left,info)
        else :              #값이 없다면 바로 부모노드 왼쪽값으로 노드 삽입
            parent.left = Node(info)
    else:
        if parent.right:
            add_node(parent.right,info)
        else:
            parent.right = Node(info)