[Algorithm] Programmers :: 길 찾기 게임

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

프로그래머스

struct Node
{
    int index; 
    int x;
    int y;
    Node* left;
    Node* right;
};
 
bool cmp(const vector<int>& a, const vector<int>& b)
{
    if (a[1] == b[1])
    {
        return a[0] < b[0];
    }
 
    return a[1] > b[1];
}
 
void makeTree(Node* root, Node* node)
{
    if (node->x < root->x) // root노드보다 왼쪽에 있다면,
    {
        if (root->left == nullptr) // 비어있으면 대입.
        {
            root->left = node;
            return;
        }
        
        makeTree(root->left, node); // 타고 내려가기.
    }
    else
    {
        if (root->right == nullptr)
        {
            root->right = node;
            return;
        }
 
        makeTree(root->right, node);
    }
}
 
vector<int> preOrderVector;
vector<int> postOrderVector;
 
void preOrder(Node* node)
{
    if (node != nullptr)
    {
        preOrderVector.push_back(node->index);
        preOrder(node->left);
        preOrder(node->right);
    }
}
 
void postOrder(Node* node)
{
    if (node != nullptr)
    {
        postOrder(node->left);
        postOrder(node->right);
        postOrderVector.push_back(node->index);
    }
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo)
{
    vector<Node> tree;
    vector<vector<int>> answer;
 
    for (int i = 0; i < nodeinfo.size(); i++)
    {
        nodeinfo[i].push_back(i + 1);
    }
 
   sort(nodeinfo.begin(), nodeinfo.end(), cmp); 
 
    for (int i = 0; i < nodeinfo.size(); i++)
    {
        tree.push_back({ nodeinfo[i][2], nodeinfo[i][0], nodeinfo[i][1] });
    }
 
    Node* root = &tree[0];
 
    for (int i = 1; i < tree.size(); i++)
    {
        makeTree(root, &tree[i]);
    }
 
    preOrder(root);
    postOrder(root);
    
    answer.push_back(preOrderVector);
    answer.push_back(postOrderVector);
    return answer;
}

 

조건에 맞게 주어진 매개변수로 트리를 구성할 노드를 만든 다음, 트리를 만들어주면 된다.

그 후 주어진 트리로 전위순회와 후위순회를 차례대로 진행하면 끝.

 

주어진 2차원벡터의 매개변수의 각 인덱스+1이 트리의 노드번호이니 sort하기 전에 먼저 값을 표시해둬야한다.

그 후에 root노드부터 최하단노드까지의 순서가 되게 sort를 해준다.

트리의 depth는 y값이 큰값일 때 root노드이니 y값으로 내림차순이 되게 한다. 

만약 값이 동일할 경우, x값이 더 작은쪽을 우선순위로 하게 cmp함수를 작성하면 된다.