[Python] 길 찾기 게임

1. 문제

 

 

 

2. 풀이 과정

방법 1) 배열로 tree를 구성한 후, 순회

import sys
sys.setrecursionlimit(10**6)

class Node(object):
    def __init__(self, i, data_set):
        self.left_idx = -1
        self.idx = i
        self.right_idx = -1
        self.num = data_set[0]
        self.x = data_set[1]
        self.y = data_set[2]
    
def pre_order(t, i, result):
    if i == -1:
        return
    result.append(t[i].num)
    pre_order(t, t[i].left_idx, result)#왼
    pre_order(t, t[i].right_idx, result)#오
    
def post_order(t, i, result):
    if i == -1:
        return
    post_order(t, t[i].left_idx, result)
    post_order(t, t[i].right_idx, result)
    result.append(t[i].num)
    
def solution(nodeinfo)
    tree = []
    #y를 기준으로 내림차순 정렬
    nodes = [(idx, xy[0], xy[1]) for idx, xy in enumerate(nodeinfo, start = 1)]
    nodes_sort = sorted(nodes, key = lambda x : x[2], reverse = True)
    node = Node(0, nodes_sort[0])
    tree.append(node)
    
    for n in nodes_sort[1:]:
        parent = 0
        new_node = Node(len(tree), n)
        while True:
            if n[1] < tree[parent].x: #왼
                if tree[parent].left_idx == -1:
                    tree[parent].left_idx = new_node.idx
                    tree.append(new_node)
                    break
                else:
                    parent = tree[parent].left_idx
            else: #오
                if tree[parent].right_idx == -1:
                    tree[parent].right_idx = new_node.idx
                    tree.append(new_node)
                    break
                else:
                    parent = tree[parent].right_idx
    
    result = [[] for _ in range(2)]
    pre_order(tree, 0, result[0])
    post_order(tree, 0, result[1])
    return result

 

방법 2) level 값으로 다음 층의 node를 찾으면서 순회

import sys
sys.setrecursionlimit(10**6)

def solution(nodeinfo):
    #존재하는 level 내림차순 정렬
    levels = sorted({x[1] for x in nodeinfo}, reverse = True)
    #y는 내림차순 우선순위, x는 오름차순 정렬
    nodes = sorted(list(zip(range(1, len(nodeinfo)+1), nodeinfo)), key = lambda x:(-x[1][1], x[1][0]))
    pre = []
    post = []
    order(levels, 0, nodes, pre, post)
    return [pre, post]
    
#cur: 현재 돌고 있는 level
def order(level, cur, nodes, pre, post):
    if not nodes:
        return
    nodes_c = nodes[:]
    root = nodes_c.pop(0)
    pre.append(root[0])
    
    for node in nodes_c:
        if level[cur+1] == node[1][1]:
            if node[1][0] < root[1][0]:#왼
                order(level, cur+1, [i for i in nodes_c if i[1][0] < root[1][0]], pre, post)
            else:#오
                order(level, cur+1, [i for i in nodes_c if i[1][0] > root[1][0]], pre, post)
    post.append(root[0])