[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 by 파이썬 (Python) : 트리 순회

https://school.programmers.co.kr/learn/courses/30/lessons/42892?language=python3 

프로그래머스

 

난이도

LV3

 

 

문제 설명 

노드들이 좌표값으로 주어지고 이진트리를 만들어 전위 순회, 후위순회 결과를 Return해야한다.

아래의 규칙들로 트리 노드를 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

 

 

접근법

solution

1. 각 인덱스+1번(노드번호)순서로 좌표값이 주어지는데 정렬시 인덱스가 달라지므로 인덱스+1(노드번호)을 각 좌표값 뒤에 추가 해준다.
2. 루트 값을 구하기 위해 Y축 기준으로 내림차순 정렬한 배열(top)을 만든다. top[0]이 루트 노드가 된다.
3. X축을 기준으로 오름차순 정렬한 배열 (left)을 만든다 left[0]이 가장 왼쪽에 있는 노드가 된다.
4. preorder, posrtoder을 실행한다.
5. 두 실행한 결과 값을 Return해준다.

 

preorder 

1. Y축기준 내림차순 정렬된 배열을 이용해 루트노드를 저장한다.
2. X축 기준 오름차순 정렬된 배열에서 해당 루트노드의 index번호 를 찾아 저장한다. (해당 인덱스 번호 기준 왼쪽, 오른쪽 노드 구분 가능)
3. 루트 노드 top[0]번을 제외한 1번 부터 X축값을 비교한다.
4. X축값이 루트노드보다 작다면 (루트노드 왼쪽에 존재) arr_left(왼쪽배열)에 저장한다.
5. X축 값이 루트 노드보다 크다면 (루트노드 오른쪽에 존재) arr_right(오른쪽배열)에 저장한다.
6. 루트 노드의 번호를 저장해준다.
7. arr_left의 배열에 값이 있다면 루트노드의 index번호 왼쪽 배열에 대해 재귀함수를 호출한다.
8. arr_right의 배열에 값이 있다면 루트노드의 index번호 오른쪽 배열에 대해 재귀함수를 호출한다.

 

postorder

1. Y축기준 내림차순 정렬된 배열을 이용해 루트노드를 저장한다.
2. X축 기준 오름차순 정렬된 배열에서 해당 루트노드의 index번호 를 찾아 저장한다. (해당 인덱스 번호 기준 왼쪽, 오른쪽 노드 구분 가능)
3. 루트 노드 top[0]번을 제외한 1번 부터 X축값을 비교한다.
4. X축값이 루트노드보다 작다면 (루트노드 왼쪽에 존재) arr_left(왼쪽배열)에 저장한다.
5. X축 값이 루트 노드보다 크다면 (루트노드 오른쪽에 존재) arr_right(오른쪽배열)에 저장한다.
6. arr_left의 배열에 값이 있다면 루트노드의 index번호 왼쪽 배열에 대해 재귀함수를 호출한다.
7. arr_right의 배열에 값이 있다면 루트노드의 index번호 오른쪽 배열에 대해 재귀함수를 호출한다.
8. 루트 노드의 번호를 저장해준다.

 

코드

import sys
sys.setrecursionlimit(10**6)
def preorder(top, left, fanswer):
    n = top[0] # 루트노드 저장
    index = left.index(n) #중심 노드 지정
    arr_left, arr_right =[] , []

    for i in range(1, len(top)):
        if n[0] > top[i][0]: #X값 비교해서 작으면 왼쪽 
            arr_left.append(top[i])
        else:
            arr_right.append(top[i])
    
    fanswer.append(n[2]) #루트 노드 번호 저장
    if len(arr_left) > 0:
        preorder(arr_left, left[:index], fanswer)
    if len(arr_right) > 0:
        preorder(arr_right, left[index+1:], fanswer)
        
def postorder(top, left, sanswer):
    n = top[0]
    index = left.index(n)
    arr_left, arr_right =[] , []
    
    for i in range(1, len(top)):
        if n[0] > top[i][0]: #X값 비교해서 작으면 왼쪽 
            arr_left.append(top[i])
        else:
            arr_right.append(top[i])
            
    if len(arr_left) > 0:
        postorder(arr_left, left[:index], sanswer)
    if len(arr_right) > 0:
        postorder(arr_right, left[index+1:], sanswer)
    
    sanswer.append(n[2])
    
def solution(nodeinfo):
    fanswer, sanswer = [], []
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i+1)
        
    top = sorted(nodeinfo, key = lambda x : (-x[1],x[0])) #루트노드부터 정렬
    left = sorted(nodeinfo) #왼쪽부터 정렬
    preorder(top, left, fanswer)
    postorder(top, left, sanswer)
    return [fanswer, sanswer]

---

트리 순회?

https://h-castle.tistory.com/entry/%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C

[트리 순회] 알고리즘 - 트리 순회