[알고리즘 연습] 길찾기 게임 (프로그래머스 lv3, 파이썬)

문제

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

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

참고

https://inuplace.tistory.com/185?category=884573

[자료구조] 트리

• 트리 구조 및 순회에 대한 이해 필요

풀이

import sys
sys.setrecursionlimit(10**6)

class Tree:
​​​​def __init__(self,dataList):
​​​​​​​​self.data = max(dataList,key=lambda x :x[1])
​​​​​​​​leftList =list(filter(lambda x :x[0] < self.data[0] , dataList))
​​​​​​​​rightList = list(filter(lambda x :x[0] > self.data[0] , dataList))
​​​​​​​​if leftList != []:
​​​​​​​​​​​​self.left=Tree(leftList)
​​​​​​​​else :
​​​​​​​​​​​​self.left=None

​​​​​​​​if rightList != []:
​​​​​​​​​​​​self.right=Tree(rightList)
​​​​​​​​else :
​​​​​​​​​​​​self.right=None

def fix(node,preList,postList):
​​​​preList.append(node.data)
​​​​if node.left is not None:
​​​​​​​​fix(node.left,preList,postList)
​​​​if node.right is not None:
​​​​​​​​fix(node.right,preList,postList)
​​​​postList.append(node.data)

def solution(nodeinfo):
​​​​answer = []
​​​​root = Tree(nodeinfo)
​​​​postList = []
​​​​preList = []
​​​​fix(root,preList,postList)
​​​​answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,preList)))
​​​​answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,postList)))
​​​​return answer

• 재귀를 이용해 트리를 초기화
• 재귀를 이용해 트리 순회
• 순회결과 도출