문제

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

아이디어

트리를 만들자

• 트리 구조를 만드려면 root로부터 노드들을 계속 넣을 수 있어야 함
• 주어진 정보로는 노드를 넣을 수 없음

예시) [1, 2], [3, 2], [2, 3]
#
1번째 노드에서 2번째 노드는 자식도 부모도 아님

미리 정렬을 하자

- 모든 노드는 서로 다른 x값을 가진다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는
  모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는
  모든 노드의 x값은 V의 x값보다 크다.

• 위 규칙을 통해서 x가 작은 순으로 정렬하면 됨을 알 수 있음

- 최상위 레벨은 노드가 하나이기 때문에
  같은 레벨의 임의의 두 노드 사이에는
  공통의 부모가 있을 수 밖에 없음(적어도 root)
- 그 중 가장 작은 레벨의 부모를
  LUB(least upper bound)라고 하자
- 그러면 두 노드는 LUB의 서로 다른 서브 트리의 노드이다.
- 그리고 규칙에 의해 각 서브트리의 사이에
  LUB가 있음을 알 수 있다.

• 즉, x가 작은 순으로 정렬하면 항상 이진 트리 구조를 유지할 수 있음

임의의 두 노드 N1, N2에 대해
각각의 좌표를 [x1, y1], [x2, y2]라고 하자
#
x1 != x2 이고 y1 != y2 라고 하자
그러면 자식 관계가 명확하므로 이진 트리 구조 유지
#
y1 == y2라고 하자
그러면 부모가 존재함
두 노드는 부모로부터 트리 유지

정렬

bool tree_sort(pair<int, vector<int>> a, pair<int, vector<int>> b)
{
    return a.second[0] < b.second[0];
}

{
    vector<pair<int, vector<int>>> nodes;
        for (int i = 0; i < nodeinfo.size(); ++i)
            nodes.push_back({i + 1, nodeinfo[i]});

        sort(nodes.begin(), nodes.end(), tree_sort);
}

• 먼저 정렬을 했을 때 번호가 유지가 안되기 때문에 pair를 통해 번호를 저장해두고 정렬했습니다.

트리

template<class T>
void safe_delete(T* ptr)
{
    if (ptr != nullptr)
    {
        delete ptr;
        ptr = nullptr;
    }
}

class node {
public:
    explicit node(int num, int x, int y)
    : m_num(num),
    m_x(x),
    m_y(y)
    {
        
    }
    ~node () {
        safe_delete(m_left);
        safe_delete(m_right);
    }
    
public:
    node* check(node* N)
    {
        if (N->m_y < this->m_y) // sub tree
        {
            if (N->m_x < this->m_x) // left
            {
                if (m_left == nullptr)
                    m_left = N;
                else
                    m_left = m_left->check(N);
            }
            else if (N->m_x > this->m_x) // right
            {
                if (m_right == nullptr)
                    m_right = N;
                else
                    m_right = m_right->check(N);
            }
            
            return this;
        }
        else // 부모, 같은 경우는 없음
        {
            if (N->m_x < this->m_x)
                N->m_right = this;
            else if (N->m_x > this->m_x)
                N->m_left = this;
            
            return N;
        }
    }
    
    void preorder_traversal(vector<int>& arr) {
             
        arr.push_back(m_num);
        
        if (m_left != nullptr)
            m_left->preorder_traversal(arr);

        if (m_right != nullptr)
            m_right->preorder_traversal(arr);
    }
    
    void postorder_traversal(vector<int>& arr) {

        if (m_left != nullptr)
            m_left->postorder_traversal(arr);

        if (m_right != nullptr)
            m_right->postorder_traversal(arr);
                     
        arr.push_back(m_num);
    }
    
private:
    int m_num;
    int m_x;
    int m_y;
    
    node* m_left = nullptr;
    node* m_right = nullptr;
};

• check 함수
  • 새로 들어온 노드가 자식인지 부모인지를 판별합니다.
  • 부모라면 자신이 자식이 되고 부모를 반환합니다.
  • 자식이라면 nullptr이면 자식이 됩니다.
  • nullptr이 아니라면 서브 트리로 넘겨줍니다.
  • 반환 값은 해당 트리의 최상위 노드이기 때문에 자식을 교체해줍니다.
• 순회 함수
  • 전위 순회 -> 나, 왼, 오 순으로 호출
  • 후위 순회 -> 왼, 오, 나 순으로 호출

실행 코드

node* root = new node(nodes[0].first, 
                          nodes[0].second[0], 
                          nodes[0].second[1]);
for (int i = 1; i < nodes.size(); ++i)
{
    root = root->check(new node(nodes[i].first, 
                                    nodes[i].second[0], 
                                    nodes[i].second[1]));
} 

vector<int> pre;
vector<int> post;
root->preorder_traversal(pre);
root->postorder_traversal(post);
answer.push_back(pre);
answer.push_back(post);

safe_delete(root);

return answer;

마무리

• 많이 생략해서 수학적으로 완벽한 증명은 아니지만 개요 정도는 잡아줄 증명이라 생각함!