[C++] 2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임

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

프로그래머스

 

 

 

 

 

#include <bits/stdc++.h>



struct Node {
    int id;
    int x, y;
    Node* left;
    Node* right;
};

bool cmp (Node node1, Node node2) {
    if (node1.y == node2.y) {
        return node1.x < node2.x;
    }
    return node1.y > node2.y;
}

void insert(Node* p, Node* c) {
    if (p->x > c->x) {
        if (p->left == nullptr){
            p->left = c;
        }
        else {
            insert(p->left, c);
        }
    }
    else {
        if (p->right == nullptr) {
            p->right = c;
        }
        else {
            insert(p->right, c);
        }
    }
}


void preorder(std::vector<int> & ans, Node* node) {
    if (!node) return;
    ans.push_back(node->id);
    preorder(ans, node->left);
    preorder(ans, node->right);
}

void postorder(std::vector<int> & ans, Node* node) {
    if (!node) return;
    postorder(ans, node->left);
    postorder(ans, node->right);
    ans.push_back(node->id);
}


std::vector<std::vector<int>> solution(std::vector<std::vector<int>> nodeinfo) {
    std::vector<Node> nodes;
    
    for (int i = 0; i < nodeinfo.size(); ++i) {
        nodes.push_back({i + 1, nodeinfo[i][0], nodeinfo[i][1], nullptr, nullptr});
    }
    
    std::sort(nodes.begin(), nodes.end(), cmp);
    
    Node* root = &nodes[0];
    
    for (int i = 1; i < nodes.size(); ++i) {
        insert(root, &nodes[i]);
    }
    
    std::vector<std::vector<int>> answer = {{}, {}};
    preorder(answer[0], root);
    postorder(answer[1], root);
    
    return answer;
}