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

📌 문제 정보

길찾기 게임 Level 3

플랫폼

프로그래머스

유형

트리, 이진트리 구성, 순회

언어

Python 3

풀이 시간

약 90분

풀이 날짜

2026.06.01

문제 링크

바로가기 ↗

---

🧩 문제 요약

각 노드의 (x좌표, y좌표)가 주어질 때, 이를 이용해 이진트리를 구성하고 전위순회와 후위순회 결과를 구하는 문제

트리 구성 규칙:

• y좌표가 큰 노드가 위쪽(부모), 작은 노드가 아래쪽(자식)
• 같은 부모를 둔 두 자식 노드 중 x좌표가 작은 노드가 왼쪽 자식
• 한 부모에 대해 자식이 둘 이상인 경우는 없음 (x좌표가 모두 다름)

입력 조건:

• nodeinfo: 노드 번호 순서대로 [x좌표, y좌표]가 담긴 2차원 배열
• 노드 번호는 1번부터 시작

출력 조건:

• [전위순회 결과, 후위순회 결과] 형태의 2차원 배열 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

이전에 풀었던 완전이진트리 문제처럼 idx*2+1, idx*2+2 배열 인덱스로 자식을 찾으면 될 줄 알았다. y좌표 내림차순, x좌표 오름차순으로 정렬한 뒤 배열에 순서대로 담아 인덱스 연산으로 순회를 시도했다.

2단계 - 막혔던 부분

일부 테스트케이스는 통과했지만 결과가 미묘하게 틀렸다. 직접 자식 노드의 x좌표를 부모와 비교해보니, idx*2+1로 계산된 "왼쪽 자식"이 실제로는 부모보다 x좌표가 큰 경우가 있었다. 이 문제는 완전이진트리가 아니라 일반 이진트리라서, 배열 인덱스만으로는 부모-자식 관계를 보장할 수 없다는 걸 뒤늦게 깨달았다.

3단계 - 해결 실마리

완전이진트리와 일반 이진트리는 다른 개념이었다.

• 완전이진트리: 마지막 층을 제외하고 빈칸 없이 채워지는 "모양" 규칙. 배열로 표현 가능.
• 이 문제(길찾기 게임): x좌표 크기로 왼쪽/오른쪽이 결정되는 구조. 노드 개수가 늘어날수록 모양이 불규칙해져서 배열로 표현 불가능.

그래서 배열 대신 노드 객체끼리 직접 연결하는 포인터 방식으로 트리를 새로 구성해야 했다.

핵심 아이디어:

• y좌표 내림차순, x좌표 오름차순으로 정렬한 뒤, 정렬된 순서대로 노드를 하나씩 트리에 삽입
• 삽입 시 루트부터 내려가며 현재 노드의 x좌표와 비교해서 왼쪽/오른쪽 위치 탐색
• y좌표가 큰 노드부터 삽입하므로 부모가 항상 자식보다 먼저 트리에 들어가는 것이 보장됨

---

✅ 최종 풀이 코드 (딕셔너리 기반 트리 + 재귀)

import sys
sys.setrecursionlimit(300000)


def preorder(node):
    if node is None:
        return []
    ret = [node["val"]]
    ret += preorder(node["left"])
    ret += preorder(node["right"])
    return ret


def postorder(node):
    if node is None:
        return []
    ret = postorder(node["left"])
    ret += postorder(node["right"])
    ret += [node["val"]]
    return ret


def insert(root, node):
    if node["x"] < root["x"]:
        if root["left"] is None:
            root["left"] = node
        else:
            insert(root["left"], node)
    else:
        if root["right"] is None:
            root["right"] = node
        else:
            insert(root["right"], node)


def solution(nodeinfo):
    answer = [[], []]

    nodes = list(enumerate(nodeinfo))
    nodes.sort(key=lambda x: (-x[1][1], x[1][0]))

    root = {"val": nodes[0][0] + 1, "x": nodes[0][1][0], "left": None, "right": None}

    for i in range(1, len(nodes)):
        node = {
            "val": nodes[i][0] + 1,
            "x": nodes[i][1][0],
            "left": None,
            "right": None,
        }
        insert(root, node)

    answer[0] = preorder(root)
    answer[1] = postorder(root)

    return answer

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(N²)	정렬 O(N log N) + 노드 N개를 각각 삽입(insert)할 때 최악의 경우(트리가 일직선으로 뻗는 경우) 삽입 1회당 O(N)이 걸려 전체 O(N²)
공간 복잡도	O(N)	노드 N개를 딕셔너리 객체로 보관, 재귀 호출 스택도 최악의 경우 O(N)

트리가 한쪽으로 치우치면(예: x좌표가 계속 증가하는 순서로 삽입되면) 매번 루트부터 끝까지 탐색해야 해서 insert 전체가 O(N²)가 된다. 균형 트리라면 O(N log N)까지 줄일 수 있지만, 이 문제 제약조건(노드 수 ≤ 10만) 안에서는 O(N²)로도 통과 가능했다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	idx*2+1, idx*2+2 배열 인덱스로 자식을 계산 → 완전이진트리 전제인데 이 문제는 일반 이진트리라서 x좌표 관계를 무시한 채 자식이 잘못 연결됨	배열 방식을 버리고 노드 딕셔너리(val, x, left, right)로 변경, insert 함수로 x좌표 비교하며 직접 트리 구성
2차	재귀로 insert, preorder, postorder를 구현하면서 파이썬 기본 재귀 깊이 제한(1000)을 초과해 런타임 에러 발생	sys.setrecursionlimit(300000)을 추가해 재귀 깊이 제한을 늘림
3차	통과 ✅	-

---

🔄 다른 풀이 방법

클래스 + 반복문(스택) 기반

class Node:
    def __init__(self, info, num, left=None, right=None):
        self.info = info
        self.num = num
        self.left = left
        self.right = right

    def has_left(self):
        return self.left is not None

    def has_right(self):
        return self.right is not None


def make_BT(nodeinfo):
    nodes = [i for i in range(1, len(nodeinfo) + 1)]
    nodes.sort(key=lambda x: (nodeinfo[x - 1][1], -nodeinfo[x - 1][0]), reverse=True)
    root = None

    for i in range(len(nodes)):
        if root is None:
            root = Node(nodeinfo[nodes[0] - 1], nodes[0])
        else:
            parent = root
            node = Node(nodeinfo[nodes[i] - 1], nodes[i])

            while True:
                if node.info[0] < parent.info[0]:
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = node
                    break
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = node
                    break
    return root


def preorder(root, answer):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        answer[0].append(node.num)
        stack.append(node.right)
        stack.append(node.left)


def postorder(root, answer):
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node is None:
            continue
        if visited:
            answer[1].append(node.num)
        else:
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))


def solution(nodeinfo):
    answer = [[], []]
    root = make_BT(nodeinfo)
    preorder(root, answer)
    postorder(root, answer)
    return answer

딕셔너리+재귀 vs 클래스+스택 비교:

• 딕셔너리+재귀: 코드가 짧고 직관적이지만 sys.setrecursionlimit이 필요하고, 노드 수가 매우 많아지면 재귀 스택 오버플로우 위험이 있음
• 클래스+스택: while문과 스택으로 재귀를 대체해서 깊이 제한 걱정이 없지만, postorder처럼 방문 여부(visited)를 따로 관리해야 해서 구현이 더 복잡함
• 코딩테스트 환경에서는 노드 수가 정해져 있다면 재귀 방식이 빠르게 짜기 좋고, 실무처럼 입력 규모를 예측하기 어렵다면 스택 방식이 더 안전

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: 완전이진트리와 일반 이진트리는 전혀 다른 개념이다. 완전이진트리는 "모양"이 규칙적이라 배열로 표현 가능하지만, 일반 이진트리는 모양이 불규칙해서 노드 객체를 직접 연결하는 포인터 방식이 필요하다.
• ✏️ 새로 알게 된 것: 트리를 구성할 때 "어떤 기준으로 부모를 먼저 삽입할지"가 중요하다. 이 문제는 y좌표가 큰 노드(=먼저 생긴 노드)가 항상 부모이므로, y좌표 내림차순으로 정렬한 뒤 순서대로 삽입하면 부모가 항상 자식보다 먼저 트리에 들어가는 것이 자연스럽게 보장된다.
• ⚠️ 실수했던 점: 이전에 풀었던 완전이진트리 문제의 idx*2+1 공식을 그대로 가져다 썼다가 한참 헤맸다. 트리 모양이 보장되는 문제인지 아닌지부터 먼저 확인했어야 했다.
• ⚠️ 실수했던 점: 재귀로 트리를 다룰 때는 sys.setrecursionlimit을 습관적으로 상단에 추가해야 한다는 걸 다시 한번 체감했다.
• 💬 한 줄 요약: 트리 모양이 일정하지 않다면 배열이 아니라 포인터로 직접 연결하자. 그리고 재귀 쓸 땐 재귀 제한부터 늘려놓자!