2019 카카오 코딩테스트 5번 : 길 찾기 게임 (c++)

www.welcomekakao.com/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Tree {
    int x, y, index;
    Tree* left;
    Tree* right;
};

bool cmp(vector<int> a, vector<int>b) {
    if (a[1] == b[1]) {
        return a[0] < b[0];
    }
    else {
        return a[1] > b[1];
    }
}
vector<int> temp1;
vector<int> preOrder(Tree* tree) {
    temp1.push_back(tree->index);
    if (tree->left != NULL) {
        preOrder(tree->left);
    }
    if (tree->right != NULL) {
        preOrder(tree->right);
    }
    return temp1;
}
vector<int> temp2;
vector<int> postOrder(Tree* tree) {
    if (tree->left != NULL) {
        preOrder(tree->left);
    }
    if (tree->right != NULL) {
        preOrder(tree->right);
    }
    temp2.push_back(tree->index);
    return temp2;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;

    for (int i = 0; i < nodeinfo.size(); i++)
    {
        nodeinfo[i].push_back(i + 1);
    }
    sort(nodeinfo.begin(), nodeinfo.end(), cmp);

    //makeTree
    Tree root = { nodeinfo[0][0],nodeinfo[0][1],nodeinfo[0][2],NULL,NULL };
    for (int i = 1; i < nodeinfo.size(); i++)
    {
        Tree* current = &root;
        while (1) {
            if (current->x > nodeinfo[i][0]) {
                if (current->left == NULL) {
                    current->left = new Tree{ nodeinfo[i][0],nodeinfo[i][1],nodeinfo[i][2],NULL,NULL };
                    break;
                }
                else {
                    current = current->left;
                }
            }
            else {
                if (current->right == NULL) {
                    current->right = new Tree{ nodeinfo[i][0],nodeinfo[i][1],nodeinfo[i][2],NULL,NULL };
                    break;
                }
                else {
                    current = current->right;
                }
            }
        }
    }
    vector <int> preorder = preOrder(&root);
    vector <int> postorder = postOrder(&root);
    answer.push_back(preorder);
    answer.push_back(postorder);
    return answer;
}