[PS] 길 찾기 게임

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

문제 설명

---

노드의 x, y좌표 값을 입력받아 이진 트리 모양으로 완성했을 때 전위 순회와 후위 순회의 결과를 구해야 한다.

깊이가 같은 노드들의 y 좌표는 같고, 어떤 임의의 노드 V를 기준으로 왼쪽 서브 트리의 x 좌표는 모두 V(x)보다 낮고 오른쪽 서브 트리의 그것은 V(x)보다 높다.

• nodeinfo의 길이는 1 이상 10,000 이하이다.
• 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
• 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.

---

문제 해결 방법

분할 정복으로 풀 수 있을 것 같다는 느낌이 딱 온다.

사실 정렬된 리스트만 있다면 트리 순회는 O(n)으로 해결할 수 있다.

이 문제의 조건에서 알 수 있는 조건은 다음과 같다.

1. 트리 T가 주어졌을 때 y 값이 가장 큰 노드가 루트 노드다.
2. 완전 이진 트리는 아니다.

따라서 우선 각 노드의 번호를 매겨준 다음에 x 좌표를 기준으로 정렬하고 순회를 하면 될 것이다.

순회 알고리즘은 당연히 알고 있어야겠다.

---

코드 구현

import sys
sys.setrecursionlimit(10**6)

preorderAnswer = []
postorderAnswer = []

def preorder(tree):
    if len(tree) == 0:
        return
    if len(tree) == 1:
        preorderAnswer.append(tree[0][2])
        return
    
    maxY = -1
    curNode = -1
    curIdx = -1
    for idx, (x, y, n) in enumerate(tree):
        if y > maxY:
            maxY = y
            curNode = n
            curIdx = idx
    
    preorderAnswer.append(curNode)
    preorder(tree[:curIdx])
    preorder(tree[curIdx+1:])
    
def postorder(tree):
    if len(tree) == 0:
        return
    if len(tree) == 1:
        postorderAnswer.append(tree[0][2])
        return
    
    maxY = -1
    curNode = -1
    curIdx = -1
    for idx, (x, y, n) in enumerate(tree):
        if y > maxY:
            maxY = y
            curNode = n
            curIdx = idx
    postorder(tree[:curIdx])
    postorder(tree[curIdx+1:])
    postorderAnswer.append(curNode)
    
def solution(nodeinfo):
    answer = []
    for idx, n in enumerate(nodeinfo):
        n.append(idx+1)
    
    xList = sorted(nodeinfo)
    
    preorder(xList)
    postorder(xList)
    answer.append(preorderAnswer)
    answer.append(postorderAnswer)
    
    
    
    return answer

preorder 함수와 postorder 함수의 형태가 굉장히 유사할 수 밖에 없는데 그냥 복붙했다.

순회 순서만 다르다.

---

느낀점