길 찾기 게임

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

tempRoot는 필요없다.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct node
{
    int x, y, data;
    struct node * left;
    struct node * right;
}node;
 
node * root, * tempRoot;
 
vector<int> vectorPre, vectorPost;
 
vector< pair<int, vector<int> > > v;
 
void search(node * temp, node * answer)
{
    if (root == NULL)
    {
        root = (node*)malloc(sizeof(node));
 
        root->x = temp->x;
        root->y = temp->y;
        root->data = temp->data;
        root->left = root->right = NULL;
 
        tempRoot = root;
 
        return;
    }
 
    if (answer->y > temp->y && answer->x > temp->x)
    {
        if (answer->left == NULL) answer->left = temp;    
        else search(temp, answer->left);
    }
    else if (answer->y > temp->y && answer->x < temp->x)
    {
        if (answer->right == NULL) answer->right = temp;
        else search(temp, answer->right);
    }
}
 
void create(int x, int y, int data)
{
    node * temp = (node*)malloc(sizeof(node));
 
    temp->x = x; 
    temp->y = y;
    temp->data = data;
 
    temp->left = temp->right = NULL;
 
    search(temp, root);
}
 
void preOrder(node * preNode)
{
    if (preNode != NULL)
    {
        vectorPre.push_back(preNode->data);
        preOrder(preNode->left);
        preOrder(preNode->right);
    }
}
 
void postOrder(node * postNode)
{
    if (postNode != NULL)
    {
        postOrder(postNode->left);
        postOrder(postNode->right);
        vectorPost.push_back(postNode->data);        
    }
}
 
bool cmp(const pair<int, vector<int> > & a, const pair<int, vector<int> > & b)
{
    return a.second.at(1) > b.second.at(1);
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{
    vector<vector<int>> answer;
 
    for (int i = 0; i < nodeinfo.size(); i++)
        v.push_back({ i + 1, nodeinfo.at(i) });
 
    sort(v.begin(), v.end(), cmp);
 
    for (auto i : v)
        create(i.second.at(0), i.second.at(1), i.first);
 
    preOrder(root);
    postOrder(root);
 
    answer.push_back(vectorPre);
    answer.push_back(vectorPost);
 
    return answer;
}