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

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

문제

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

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

코드

이 문제를 풀기위해 class를 이용한 트리구조생성과 전위순회, 후위순회를 다시한번 공부할수있었습니다.

1. 우선 해당 문제의 조건에 맞게 class를 이용한 이진 트리(Binary Tree) 를 구현
   • 이진트리의 각각의 노드의 property는 x, y, left, right, index를 갖고있습니다.
2. 만들어진 이진트리에서 전회순회 및 후위순회를 진행

import sys
# python은 recursion depth는 최대 1000으로 제한되있다.
# 문제의 노드 갯수는 1~ 10000까지이므로 재귀의 깊이를 10000으로 늘린다.
sys.setrecursionlimit(10000)

preorder_list = []
postorder_list = []
class Node:
    def __init__(self, x,y,index):
        self.x = x
        self.y = y
        self.index = index
        self.right = None
        self.left = None

# 전위 순회 : root를 기준으로 왼쪽 서브트리 => 오른쪽 서브트리
def preorder(node):
    preorder_list.append(node.index)
    if node.left:
        preorder(node.left)
    if node.right:
        preorder(node.right)

# 후위순회 : 왼쪽 맨밑에서 시작, 왼쪽 서브트리 => 오른 서브트리
def postorder(node):
    if node.left:
        postorder(node.left)
    if node.right:
        postorder(node.right)
    postorder_list.append(node.index)

def solution(nodeinfo):
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i+1)
    nodeinfo = sorted(nodeinfo, key=lambda x:(-x[1],x[0]))
    root_node = None
    for node in nodeinfo:
        if not root_node:
            # 1. 맨 처음에 root node를 생성
            root_node = Node(node[0],node[1],node[2])
        else:
            cur_node = root_node # 현재노드
            x, y, index = node[0],node[1],node[2]   # 다음 노드
            while True:
                # 2. cur_node와 다음 노드의 x값을 비교
                if cur_node.x > x:
                    # 3. cur_node의 x가 더 크면 왼쪽을 확인
                    if cur_node.left:
                        # 4. cur_node의 왼쪽이 존재하면 해당 노드를 cur_node로 할당
                        cur_node = cur_node.left
                        continue
                    else:
                        # 4. cur_node의 왼쪽이 존재안하면 왼쪽 노드 추가
                        cur_node.left = Node(x,y,index)
                        break
                elif cur_node.x < x:
                    if cur_node.right:
                        cur_node = cur_node.right
                        continue
                    else:
                        cur_node.right = Node(x,y,index)
                        break
                break
    res = []
    preorder(root_node)
    postorder(root_node)
    res.append(preorder_list)
    res.append(postorder_list)
    return res