[2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임

문제

• 좌표가 주어졌을 때 전위 순회와 후위 순회의 결과 리턴하기
  • 자식 노드의 y값은 항상 부모 노드보다 작다.
  • V노드의 왼쪽 서브트리의 x값은 항상 V의 x값보다 작고 오른쪽 서브트리는 크다.
• 1 <= 노드 개수 <= 10,000
• 1 <= 트리 깊이 <= 1000

 

 

풀이 (1h +)

• (x좌표, y좌표, 노드 번호)에서 x좌표를 기준으로 정렬한다.
• 루트를 구한 뒤, 전위 순회와 후위 순회를 한다.
  • 전위 순회 : 루트 - 왼쪽 - 오른쪽
  • 후위 순회 : 오른쪽 - 왼쪽 - 루트
• 루트의 x좌표가 7이면 왼쪽 sub tree 는 x좌표가 7보다 작아야 하고 오른쪽 sub tree는 7보다 커야 한다.
  따라서 루트의 x좌표의 인덱스를 기준으로 각각의 sub tree를 구분할 수 있다.
• 각 sub tree의 순회는 재귀를 통해 순회를 반복한다

 

import sys
sys.setrecursionlimit(10**4)

# 루트 찾기
def find_root(coord_x) :
    rx, ry, ri, x_idx = 0, 0, 0, 0
    for idx, (x, y, i) in enumerate(coord_x) :
        if y >= ry :
            rx, ry, ri, x_idx = x, y, i, idx
    return rx, ry, ri, x_idx

# 트리 순회하기
# 전위 순회 : 루트 - 왼쪽 - 오른쪽
# 후위 순회 : 오른쪽 - 왼쪽 - 루트
def treeorder(coord_x, order, how="pre") :
    rx, ry, ri, x_idx = find_root(coord_x)	# 루트 찾기

    if how == "pre" :           # 루트 (전위 순회)
        order += [ri]			 
    if x_idx > 0 :              # 왼쪽 자식
        order += treeorder(coord_x[:x_idx], [], how)
    if x_idx < len(coord_x)-1 : # 오른쪽 자식
        order += treeorder(coord_x[x_idx+1:], [], how)
    if how == "post" :          # 루트 (후위 순회)
        order += [ri]
        
    return order

    
def solution(nodeinfo):
    n = len(nodeinfo)   # 노드 개수
    # nodeinfo : (x좌표, y좌표, 노드 번호)
    nodeinfo = [(x, y, i+1) for i, (x, y) in enumerate(nodeinfo) ] 
    coord_x = sorted(nodeinfo, key=lambda x: x[0])  # x좌표 순으로 정렬
    
    return [treeorder(coord_x, [], "pre"), treeorder(coord_x, [], "post")]