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

1. 문제

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

 

2. 코드

python 1

import sys
sys.setrecursionlimit(10**6)

def preorder(y, x, answer):
    node = y[0]
    idx = x.index(node)
    left, right = [], []
    
    for i in range(1, len(y)):
        if node[0] > y[i][0]: right.append(y[i])
        else: left.append(y[i])
    
    answer.append(node[2])
    if len(right) > 0: preorder(right, x[:idx], answer)
    if len(left) > 0 : preorder(left, x[idx + 1:], answer)
    

def postorder(y, x, answer):
    node = y[0]
    idx = x.index(node)
    left, right = [], []
    
    for i in range(1, len(y)):
        if node[0] > y[i][0]: right.append(y[i])
        else: left.append(y[i])
    
    if len(right) > 0: postorder(right, x[:idx], answer)
    if len(left) > 0 : postorder(left, x[idx + 1:], answer)
    answer.append(node[2])
    
def solution(nodeinfo):
    nodeinfo = [[*info, idx + 1] for idx, info in enumerate(nodeinfo)]
    y = sorted(nodeinfo, key = lambda x : -x[1])
    x = sorted(nodeinfo)
    
    preorderList = []
    postorderList = []
    
    preorder(y, x, preorderList)
    postorder(y, x, postorderList)
    
    return [preorderList, postorderList]

풀이

1. 트리를 담는 구조 생성
   1. y - 내림차순 정렬 root 노드 찾을 때 사용
   2. x - 오름자순 정렬 sub 트리 찾을 때 사용
2. preorder 함수 생성
   1. preorder의 순서는 root → left → right이다
   2. 현재 root 노드 → y[0]
      1. root 노드를 기준으로 x 값이 작으면 → right에 저장
      2. root 노드를 기준으로 x 값이 크면 → left에 저장
   3. root 노드 방문
   4. right, left 재귀 호출
3. postorder 함수 생성
   1. postorder의 순서는 left → right → root이다
   2. 현재 root 노드 → y[0]
      1. root 노드를 기준으로 x 값이 작으면 → right에 저장
      2. root 노드를 기준으로 x 값이 크면 → left에 저장
   3. right, left 재귀 호출
   4. root 노드 방문
4. 순회 결과 출력

 

python 2

import sys
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, x, y, idx):
        self.x = x
        self.y = y
        self.idx = idx
        self.left = None
        self.right = None

def build_tree(nodes, Lx, Rx):
    if not nodes:
        return None

    root = nodes[0]
    root_node = Node(root[0], root[1], root[2])
    left_nodes = []
    right_nodes = []

    for node in nodes[1:]:
        x, y, idx = node
        if Lx <= x < root[0]:
            left_nodes.append(node)
        elif root[0] < x <= Rx:
            right_nodes.append(node)

    root_node.left = build_tree(left_nodes, Lx, root[0] - 1)
    root_node.right = build_tree(right_nodes, root[0] + 1, Rx)

    return root_node

def preorder(node, result):
    if node:
        result.append(node.idx)
        preorder(node.left, result)
        preorder(node.right, result)

def postorder(node, result):
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.idx)

def solution(nodeinfo):
    nodeinfo = [[x, y, idx + 1] for idx, (x, y) in enumerate(nodeinfo)]
    nodeinfo.sort(key=lambda x: (-x[1], x[0]))  # y 내림차순, x 오름차순

    root = build_tree(nodeinfo, 0, 100000)  # x 범위 넉넉하게 설정

    preorder_result = []
    postorder_result = []

    preorder(root, preorder_result)
    postorder(root, postorder_result)

    return [preorder_result, postorder_result]

 

3. 메모

• preorder, postorder 자체는 어려운 내용이 아님
• x,y를 통해서 현재 노드, left와 right를 어떻게 구현할지가 point → 이게 생각하기 쉽지 않았음
  • y가 root가 무엇인지 알려주는것, x는 y가 같은 위치일때 left, right비교 하기 위해 사용
• Python 1 방식은 구현이 간단하지만 시간복잡도 O(N²)로 비효율적
• Python 2는 트리 전체를 좌표 범위 기반으로 한 번에 구성 → O(N log N)