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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42892

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

 

문제는 간단하다.

좌표를 주고 이를 이진트리로 구성해서 전위,후위 탐색을 수행한 결과 값을 내놔라 이다.

 

트리 구성은 재귀로 구현했다.

우선 좌표를 정렬했다. y는 작아지게 x좌표는 커지게 정렬하게 되면 부모 노드부터 순서대로 정렬이 된다.

그리고 가장 첫번째 값이 부모노드가 된다.

 

이제 부모노드를 트리에 넣고 시작한다.

 

왼쪽은 자신보다 y 좌표가 작은 노드가 오른쪽은 자신보다 y좌표가 큰 노드가 들어가게 문제에서 트리를 구성하라고 한다.

그래서 조건에 방향에 자식 노드가 있다면 그 자식으로 들어가서 다시 조건을 체크한다.

하지만 없다면 그 자리에 넣으려는 정보 가지고 노드를 생성해서 넣어주면 된다.

 

전위 탐색은 부모,왼쪽,오른쪽 순으로 탐색하는 것이고

후위 탐색은 왼쪽,오른쪽,부모 순으로 탐색하는 방식이다.

이는 재귀로 간단하게 구현할 수 있다.

 

그리고 노드가 최대 1만개가 주어진다. 만약 트리가 한쪽 방향으로만 쭉 이어진 편향이진트리일 경우 최대 재귀가 1만번 돌게 된다. 파이썬은 기본 1000만 돌도록 되어 있기 때문에 이를 setrecursionlimit로 늘려줘야한다.

늘리지않는다면 테케 6,7번인가 런타임 에러가 날 것이다.

from sys import setrecursionlimit
setrecursionlimit(10000)
class Node(object):
    def __init__(self, info):
        self.num = info[2]
        self.pos = info[:2]
        self.left = None
        self.right = None
        
def solution(nodeinfo):
    answer = [[]]
    for idx in range(len(nodeinfo)):
        nodeinfo[idx].append(idx+1)
    
    nodeinfo.sort(key=lambda x :(-x[1],x[0]))
    tree = Node(nodeinfo[0])
    
    for info in nodeinfo[1:]:
        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]:
        if parent.left:
            add_node(parent.left,info)
        else:
            parent.left = Node(info)
    else:
        if parent.right:
            add_node(parent.right,info)
        else:
            parent.right = Node(info)