(Python) 프로그래머스 - 길 찾기 게임

17 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

import sys
from collections import deque
sys.setrecursionlimit(10**6)

def solution(nodeinfo):
    # 레벨과 (y 내림차순, x 오름차순)으로 데이터 정리
    nodes=[]
    levels = set()
    for num, node in enumerate(nodeinfo,start=1):
        nodes.append((num,node))
        levels.add(node[1])
    nodes.sort(key=lambda x:(-x[1][1],x[1][0]))
    nodes = deque(nodes)
    levels = sorted(list(levels),reverse=True)

    pre_order = []
    post_order = []
    order(nodes,levels,0,pre_order,post_order)
    return[pre_order,post_order]


def order(nodes,levels,cur_level_idx,pre_order,post_order):
    cur = nodes.popleft()
    pre_order.append(cur[0]) # 전위

    if nodes:
        for _, node in nodes:
            if node[1] == levels[cur_level_idx+1]:
                # left child, 왼쪽 자식 트리에 대한 순회
                if node[0] <cur[1][0] : 
                    order(deque([x for x in nodes if x[1][0] < cur[1][0]]),levels,cur_level_idx+1,pre_order,post_order)
                # right child, 오른쪽 자식 트리에 대한 순회
                else:
                    order(deque([x for x in nodes if x[1][0] > cur[1][0]]), levels, cur_level_idx + 1, pre_order, post_order)
                    break
    # 후위
    post_order.append(cur[0])