[프로그래머스 Lv.3] 길 찾기 게임 (Python)

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

프로그래머스

풀이

이진트리, 전위 순회, 후위 순회를 사용한 문제로 알고리즘 문제 풀이를 하다 보면 종종 나타나기에 구현을 해본 경험이 있어 레벨 3 문제치고는 쉽게 풀 수 있었다. 그렇지만 좌표를 사용해서 트리를 그려야 한다는 점, 좌표뿐만 아니라 nodeinfo 내에서 위치한 번호도 알고 있어야 한다는 점이 기존의 이진트리를 사용한 문제가 달랐다고 할 수 있겠다.

 

우선, 트리의 레벨은 y좌표에 의해 결정되기에 y좌표를 내림차순으로 정렬하여 루트부터 리프까지 트리를 그릴 수 있도록 한다. 다음으로, 루트부터 시작해 노드들을 하나씩 트리에 붙인다. 트리에 노드를 붙이는 방식은 기존의 이진트리에서의 방식과 동일하게 진행하면 된다. 마지막으로, 모든 노드를 붙인 트리를 전위 순회, 후위 순회한 값을 반환하면 풀이가 끝난다.

 

위와 같이 풀이하고 제출을 했더니, 2~3개의 테스트 케이스에서 런타임 에러가 발생했다. 원인을 파악하려고 Q&A를 찾아보니, 재귀 깊이 제한 때문이었다. 재귀 깊이 제한을 늘리니 최종적으로 통과할 수 있었다.

import sys
sys.setrecursionlimit(10**9) # 재귀 제한 깊이를 늘림

class Node: # Node 클래스 선언
    def __init__(self, info):
        self.idx = info[0] # 노드의 번호
        self.x = info[1] # 노드의 x좌표
        self.y = info[2] # 노드의 y좌표
        self.left = None # 노드의 왼쪽 자식
        self.right = None # 노드의 오른쪽 자식
        
def add_node_to_tree(root, node): # root부터 시작하여 node들을 붙여 트리를 생성하는 메서드
    if root.x > node.x: # 붙여야할 node의 x좌표가 root의 x좌표보다 작은 경우, 왼쪽 서브 트리에 붙이기
        if not root.left: root.left = node # 왼쪽 자식이 없을 경우에, 왼쪽 자식으로 붙이기
        else: add_node_to_tree(root.left, node) # 왼쪽 자식이 있을 경우, 왼쪽 자식을 루트로 하여 메서드 재귀적으로 실행
    else: # 오른쪽 서브 트리에 붙이기
        if not root.right: root.right = node
        else: add_node_to_tree(root.right, node)

def solution(nodeinfo):
    nodeinfo = [(idx+1, x, y) for idx, (x, y) in enumerate(nodeinfo)] # nodeinfo에서의 번호와 x,y 좌표를 하나의 튜플로 저장
    
    nodeinfo.sort(key=lambda x: -x[2]) # y좌표를 내림차순으로 정렬
    root = Node(nodeinfo[0]) # y좌표가 가장 큰 node는 root
    
    for info in nodeinfo[1:]: # root를 제외한 모든 node를 순회하며
        add_node_to_tree(root, Node(info)) # 트리에 붙이기
        
    answer = [[], []]
    def preorder(root): # 전위 순회 메서드
        if not root: return
        
        answer[0].append(root.idx)
        preorder(root.left)
        preorder(root.right)

    def postorder(root): # 후위 순회 메서드
        if not root: return
        
        postorder(root.left)
        postorder(root.right)
        answer[1].append(root.idx)
    
    preorder(root)
    postorder(root)
        
    return answer