[프로그래머스] 길 찾기 게임 / 파이썬 / 자료구조(트리)

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

코딩테스트 연습 - 길 찾기 게임

풀이

자료구조를 적절히 사용하는지를 묻는 문제였던 것 같다.

이진트리를 한 번 구현해 본 경험이 있으면 쉽게 풀 수 있는 문제였다.

우선 높이별로 한 번 정렬을 한 다음에, 이진트리에 계속 추가하는 형식으로 문제를 풀었다.

딱히 설명이 필요없을 듯 하다..

import heapq as h
import sys
sys.setrecursionlimit(100000)
answer = [[], []]

class Node:
    right_child = None
    left_child = None
    x = None
    y = None
    idx = None

    def __init__(self, x, y, idx):
        self.x = x
        self.y = y
        self.idx = idx

    def insert(self, newNode):
        nx, ny = newNode.x, newNode.y
        # 오른쪽으로 가야함
        if nx > self.x:
            if self.right_child == None:
                self.right_child = newNode
            else:
                self.right_child.insert(newNode)
        # 왼쪽으로 가야함
        else:
            if self.left_child == None:
                self.left_child = newNode
            else:
                self.left_child.insert(newNode)

    def preorder(self):
        global answer
        answer[0].append(self.idx)
        if self.left_child != None:
            self.left_child.preorder()
        if self.right_child != None:
            self.right_child.preorder()

    def postorder(self):
        global answer
        if self.left_child != None:
            self.left_child.postorder()
        if self.right_child != None:
            self.right_child.postorder()
        answer[1].append(self.idx) 

def solution(nodeinfo):
    global answer
    # idx 순서 넣기
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i+1)
    # 높이에 따라 정렬
    nodeinfo = sorted(nodeinfo, key=lambda n: (-n[1], n[0]) )
    # 가장 위에 있는 노드
    rootNode = None

    for x, y, idx in nodeinfo:
        newNode = Node(x, y, idx)
        if rootNode == None:
            rootNode = newNode
        else:
            rootNode.insert(newNode)
    rootNode.preorder()
    rootNode.postorder()
    return answer