Level 3. 길 찾기 게임

Level 3. 길 찾기 게임

 

 

이진 트리를 구현하고, 좌표의 우선순위가 레벨 순회 순서로 되게끔 트리에 삽입한 후 전위 순회나 후위 순회를 하는 문제다.

 

좌표과 레벨 순회 순서가 되게 하려면, Y 좌표가 큰 것을 우선으로 하되 같은 경우 X 좌표가 작은 것을 선택하면 된다.

 

트리 구현을 정말 오랜만에 해보는데 학교 자료구조 시간에 워낙 실습을 많이 해서 그런지, 기어이 새록새록 떠올라 어렵지 않게 할 수 있었다.

• 삽입할 위치의 부모를 찾을 때는 X 좌표만 비교하면서 Up-down 형식으로 재귀적으로 찾으면 된다.

 

전위/중위/후위 순회 모두 재귀를 사용하면 쉽게 구현할 수 있다.

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Point
{
    int id;
    int x;
    int y;

    friend bool operator < (const Point& A, const Point& B)
    {
        if (A.y == B.y)
            return A.x < B.x;
        else
            return A.y > B.y;
    }
};

class Tree
{
private:
    struct Node
    {
        int id;
        int x;

        Node* left  = nullptr;
        Node* right = nullptr;
    };

    Node* root;

public:
    Tree() : root(nullptr) {}

    void add(const Point& point)
    {
        if (root == nullptr)
        {
            root = new Node;

            root->id = point.id;
            root->x  = point.x;
        }
        else
        {
            Node* p = findParent(root, point.x);
            Node* child = new Node;

            if (p->x < point.x)
                p->right = child;
            else
                p->left = child;

            child->id = point.id;
            child->x  = point.x;
        }
    }

private:
    Node* findParent(Node* p, int x)
    {
        if (p->x < x)
            if (p->right)
                return findParent(p->right, x);
            else
                return p;
        else
            if (p->left)
                return findParent(p->left, x);
            else
                return p;
    }

    void preOrder(Node* p, vector<int>& result)
    {
        if (p == nullptr)
            return;

        result.emplace_back(p->id);
        preOrder(p->left, result);
        preOrder(p->right, result);
    }

    void postOrder(Node* p, vector<int>& result)
    {
        if (p == nullptr)
            return;

        postOrder(p->left, result);
        postOrder(p->right, result);
        result.emplace_back(p->id);
    }

    void deleteAll(Node* p)
    {
        if (p == nullptr)
            return;

        deleteAll(p->left);
        deleteAll(p->right);
        delete p;
    }

public:
    vector<int> preOrder()
    {
        vector<int> result;

        preOrder(root, result);

        return result;
    }

    vector<int> postOrder()
    {
        vector<int> result;

        postOrder(root, result);

        return result;
    }

    ~Tree()
    {
        deleteAll(root);
    }
};

vector<vector<int>> solution(vector<vector<int>> nodeinfo)
{
    vector<vector<int>> answer;
    set<Point> st;

    for (int i = 0; i < nodeinfo.size(); ++i)
        st.insert({i + 1, nodeinfo[i][0], nodeinfo[i][1]});

    Tree tr;

    for (const Point& p : st)
        tr.add(p);

    answer.emplace_back(tr.preOrder());
    answer.emplace_back(tr.postOrder());

    return answer;
}