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

문제 링크

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

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

 

풀이 - 다른 블로그 참고 

1. nodes 배열에 노드의 위치, 노드 번호 저장 

2. nodes를 y 좌표는 내림차순, x 좌표는 오름차순 정렬

- y 좌표가 가장 큰 것이 루트 노드, 그리고 차례대로 y좌표따라 내려가면서 왼쪽부터 x 좌표 기준으로 이진 노드로 채우면 됨 

3. preorder 실행 

- 중심이 될 루트 노드 기준으로 x 좌표 값 비교해서 작으면 왼쪽 트리에 추가, 크면 오른쪽 트리에 추가

- 전위 순회이므로 answer에 현재 노드 추가 -> 왼쪽 트리 순회 -> 오른쪽 트리 순회 순으로 재귀 함수 실행 

4. postorder 실행

- 중심이 될 루트 노드 기준으로 x 좌표 값 비교해서 작으면 왼쪽 트리에 추가, 크면 오른쪽 트리에 추가

- 후위 순회이므로 왼쪽 트리 순회 -> 오른쪽 트리 순회 ->  answer에 현재 노드 추가 순으로 재귀 함수 실행 

import sys
sys.setrecursionlimit(10**6)

def preorder(nodes, answer):
    # 중심이 될 루트 노트 
    node = nodes[0]
    # 왼쪽 트리 노드
    left = []
    # 오른쪽 트리 노르 
    right = [] 
    
    for i in range(1, len(nodes)):
        # x 좌표 값 비교
        # 작으면 왼쪽에 위치 
        if node[0] > nodes[i][0]:
            left.append(nodes[i])
        # 크면 오른쪽에 위치 
        else:
            right.append(nodes[i])
            
    # 전위 순회 이므로 
    answer.append(node[2])
    
    if len(left) > 0 :
        preorder(left, answer)
    if len(right) > 0 :
        preorder(right, answer)
    
    return 
    
def postorder(nodes, answer):
    # 중심이 될 루트 노트 
    node = nodes[0]
    # 왼쪽 트리 노드
    left = []
    # 오른쪽 트리 노르 
    right = [] 
    
    for i in range(1, len(nodes)):
        # x 좌표 값 비교
        # 작으면 왼쪽에 위치 
        if node[0] > nodes[i][0]:
            left.append(nodes[i])
        # 크면 오른쪽에 위치 
        else:
            right.append(nodes[i])
    
    if len(left) > 0 :
        postorder(left, answer)
    if len(right) > 0 :
        postorder(right, answer)
        
    # 후회 순회이므로 제일 마지막 
    answer.append(node[2])
    return 
    
def solution(nodeinfo):
    answer = [[]]
    nodes = [] 
    
    # 노드 위치, 노드 번호 저장
    for i in range(len(nodeinfo)):
        nodes.append((nodeinfo[i][0], nodeinfo[i][1], i + 1 ))
        
    # y 기준 내림차순, x 기준 오름차순 정렬 
    nodes = sorted(nodes, key = lambda x : (-x[1], x[0]))
    
    # 전위 순회 결과값 저장 
    preanswer = []
    # 후위 순회 결과값 저장 
    postanswer = []
    
    preorder(nodes, preanswer)
    postorder(nodes, postanswer)
    
    return [preanswer, postanswer]