[Python] 프로그래머스 코딩테스트 연습 - 2019 KAKAO BLIND RECRUITMENT > 길 찾기 게임

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

프로그래머스

 

트리를 구축하는 과정이 어려워서 많이 헤맸다😅

다른 사람들의 코드를 많이 참조하여 풀었고, 대신 최대한 분석을 많이 해서 확실히 이해하려고 노력했음

 

1. 트리 구축하기 + 재귀형식으로 전위/후위 순회

import sys
def solution(nodeinfo) :

    sys.setrecursionlimit(10**6)    # 최대 재귀 횟수 설정 (프로그래머스 환경 설정 재귀 횟수 초과 에러 방지)

    # nodeinfo에는 각 노드의 좌표만 있음
    # y가 같으면 같은 레벨, x의 위치로 좌우 서브트리 판단
    # 부모/자식 관계를 저장하고 전위/후위 순회 메서드 만들기

    node_list = [ ]
    for index, xy in enumerate(nodeinfo) :
        node_list.append(Node(index, xy))

    node_list.sort(key=lambda x : (-x.xy[1], x.xy[0]))  # y값 내림차순, x값 오름차순 정렬

    root = None
    for node in node_list :

            if root : # 루트가 있는 경우 (맨 처음 빼고 전부 이쪽 로직)
                parent = root   # 루트부터 자리 탐색 시작

                while True : # 자리 찾을 때까지 반복
                    if parent.xy[0] > node.xy[0] :   # 부모 노드보다 왼쪽일 경우
                        if parent.left :    # 부모에 이미 왼쪽 서브트리가 있으면
                            parent = parent.left    # 부모의 왼쪽 서브트리를 부모로 두고 다시 탐색
                            continue
                        else :      # 왼쪽 서브트리가 없으면
                            parent.left = node  # 현재 노드를 부모의 왼쪽 서브트리로 지정
                            break   # 자리를 찾았으므로 while문 나가기

                    else :  # 부모 노드보다 오른쪽일 경우 (이하 로직은 왼쪽의 경우와 동일)
                        if parent.right :
                            parent = parent.right
                            continue
                        else :
                            parent.right = node
                            break

            else :  # 루트가 없는 경우 (맨 처음 루트일 때만 이쪽)
                root = node

    return [preorder(root), postorder(root)]


def preorder(node) :
    # 전위 순회 순서 : 현재 -> 왼쪽 -> 오른쪽
    # 리턴할 값은 순회할 노드의 인덱스+1을 배열 형식으로
    answer = [node.index + 1]

    if node.left :
        answer += preorder(node.left)
    if node.right :
        answer += preorder(node.right)

    return answer


def postorder(node) :
    # 후위 순회 순서 : 왼쪽 -> 오른쪽 -> 현재
    # 리턴할 값은 순회할 노드의 인덱스+1을 배열 형식으로
    answer = [ ]

    if node.left :
        answer += postorder(node.left)
    if node.right :
        answer += postorder(node.right)
    answer += [node.index + 1]

    return answer


class Node :
    def __init__(self, index, xy):
        self.index = index
        self.xy = xy
        self.left = None
        self.right = None

 

 

✅ 참고 : 재귀함수 최대 깊이 설정

 

import sys

sys.setrecursionlimit(10**6)    # 최대 재귀 횟수 설정

 

프로그래머스에서 재귀함수의 최대 깊이가 기본 1000회로 지정되어 있기 때문에 그 이상 반복되는 재귀함수가 존재할 경우 런타임 에러가 발생한다.

이를 방지하기 위해 위와 같은 코드를 추가해 최대 재귀 횟수를 늘려주어야 한다.

 

 

다음은 비재귀 방식으로 전위/후위 순서를 구하는 코드이다.

 

---

2. 전위/후위순회를 비재귀형식으로 구하기

def preorder(node) :
    # 전위 순회 순서 : 현재 -> 왼쪽 -> 오른쪽
    # 리턴할 값은 순회할 노드의 인덱스+1을 배열 형식으로
    answer = []
    stack = [node]
    while stack :
        this_node = stack.pop()

        if this_node :
            answer.append(this_node.index + 1)
            stack.append(this_node.right)
            stack.append(this_node.left)

    return answer


def postorder(node) :
    # 후위 순회 순서 : 왼쪽 -> 오른쪽 -> 현재
    # 리턴할 값은 순회할 노드의 인덱스+1을 배열 형식으로
    answer = []
    stack = [(node, False)]
    while stack :
        this_node, visited = stack.pop()

        if this_node:
            if visited :
                answer.append(this_node.index + 1)
            else :
                stack.append((this_node, True))
                stack.append((this_node.right, False))
                stack.append((this_node.left, False))

    return answer