2019 KAKAO BLIND RECRUITMENT / 길 찾기 게임

1. 2019 KAKAO BLIND RECRUITMENT
2. 길 찾기 게임

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Node {
public:
    int n;
    Node* l;
    Node* r;
    int x;
    int y;
};

void make(Node* r, Node* n) {
    if (n->x < r->x) {
        if (!r->l) {
            r->l = n;
            return;
        }
        make(r->l, n);
        return;
    }

    if (!r->r) {
        r->r = n;
        return;
    }
    make(r->r, n);
}

void dfs(Node* r, vector<int> &v) {
    if (!r) return;
    v.push_back(r->n + 1);
    dfs(r->l, v);
    dfs(r->r, v);
}

void dfs_post(Node *r, vector<int>& v) {
    if (!r) return;
    dfs_post(r->l, v);
    dfs_post(r->r, v);
    v.push_back(r->n + 1);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> order;
    for (int i = 0; i < nodeinfo.size(); ++i) {
        order.push_back({ nodeinfo[i][1], i });
    }
    sort(order.begin(), order.end(), greater<>());
    vector<Node> v(nodeinfo.size());

    int t = order[0][1];
    Node* root = &v[0];
    root->n = t;
    root->x = nodeinfo[t][0];
    root->y = nodeinfo[t][1];
    root->l = root->r = 0;

    for (int i = 1; i < order.size(); ++i) {
        int id = order[i][1];
        int x = nodeinfo[id][0];
        int y = nodeinfo[id][1];
        v[i].n = id;
        v[i].x = x;
        v[i].y = y;
        v[i].l = v[i].r = 0;
        make(root, &v[i]);
    }
    vector<int> in, post;
    dfs(root, in);
    dfs_post(root, post);
    vector<vector<int>> answer;
    answer.push_back(in);
    answer.push_back(post);
    return answer;
}

int main() {
    solution({ {5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2} });
    return 0;
}