프로그래머스 - 길 찾기 게임

프로그래머스 - 길 찾기 게임

바이너리트리 만들고 전위, 후위 순회만 구현하면 된다.

초기에 주어진 노드들의 순서가 무작위이기 때문에 Root부터 시작해서 Height가 높은 노드(y값이 높은 노드들)부터 미리 정렬해둔 뒤 바이너리트리에 Insert해주면 된다.

코드는 다음과 같다.

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

using namespace std;

bool compare(const vector<int> &a, const vector<int> &b)
{
    if(a[1] == b[1])
        return a[0] < b[0];
    return a[1] > b[1];
}

typedef struct __node {
    int x;
    int y;
    int idx;
} node;

typedef struct __tree_node {
    int x;
    int idx;
    struct __tree_node *left;
    struct __tree_node *right;
} tree_node;

vector<vector<int>> answer;

void preorder(tree_node *n) 
{
    answer[0].push_back(n->idx);
    if(n->left)
        preorder(n->left);
    if(n->right)
        preorder(n->right);
}

void postorder(tree_node *n)
{
    if(n->left)
        postorder(n->left);
    if(n->right)
        postorder(n->right);
    answer[1].push_back(n->idx);
}

tree_node *get_new_node(int x, int idx)
{
    tree_node *new_node = new tree_node();
    new_node->x = x;
    new_node->idx = idx;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;    
}

void insert_node(int x, int idx, tree_node *root)
{
    tree_node *cur = root;
    while(1) {
        if(x < cur->x) {
            if(!cur->left) {
                cur->left = get_new_node(x, idx);
                break;
            } else 
                cur = cur->left;
        } else {
            if(!cur->right) {
                cur->right = get_new_node(x, idx);
                break;
            } else 
                cur = cur->right;
        }
    }
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {

    answer.resize(2);
    int cur = 1;
    for(auto &it : nodeinfo) 
        it.push_back(cur++);
    sort(nodeinfo.begin(), nodeinfo.end(), compare);
    
    vector<vector<node>> node_list(1001);
    
    cur = 0;
    node_list[cur].push_back( {nodeinfo[cur][0], nodeinfo[cur][1], nodeinfo[cur][2]} );
    for(int i=1;i<nodeinfo.size();i++) {
        if(nodeinfo[i][1] != node_list[cur][0].y) 
            cur++;
        node_list[cur].push_back( { nodeinfo[i][0], nodeinfo[i][1], nodeinfo[i][2] } );
    }
    
    tree_node *root = get_new_node(node_list[0][0].x, node_list[0][0].idx); 
    for(int i=1;i<=cur;i++) 
        for(auto it : node_list[i]) 
            insert_node(it.x, it.idx, root);
    
    preorder(root);
    postorder(root);
    
    return answer;
}