programmers 길 찾기 게임

programmers 길 찾기 게임 : programmers.co.kr/learn/courses/30/lessons/42892

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

 

2019 kakao blind recruitment Level3 문제인 길 찾기 게임입니다.

 

트리를 만들 수 있도록 모든 정점을 노드로 변환해 준 후에 

1개씩 순회하면서 알맞은 위치에 넣어주시면 됩니다.

 

정확한 설명은 주석을 통하여 작성하였습니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct node{
    int x,y,idx;
    node* left;
    node* right;
};

node* insertNode(node* parent, node* now){ // 일반적인 바이너리 트리의 삽입 형태 입니다.
    if(parent == NULL) return now;
    if(parent->x > now->x) parent->left = insertNode(parent->left, now);
    else parent->right = insertNode(parent->right, now);
    return parent;
}

vector<int> pre;
vector<int> post;

void preorder(node* now){ // 전위순회
    if(now == NULL) return;
    
    pre.push_back(now->idx);
    preorder(now->left);
    preorder(now->right);
}

void postorder(node* now){ // 후위순회
    if(now == NULL) return;
    
    postorder(now->left);
    postorder(now->right);
    post.push_back(now->idx);
}

bool cmp(node& A, node& B){ // y를 오름차순, x를 내림차순 정렬해줍니다.
    if(A.y != B.y) return A.y > B.y;
    return A.x < B.x;
}

vector<node> v;

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    for(int i = 0; i<nodeinfo.size(); i++){ // 정점을 노드화 해줍니다.
        v.push_back({nodeinfo[i][0], nodeinfo[i][1], i+1});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    node* root = &v[0]; // y가 가장 큰 값이 루트노드가 됩니다.
    for(int i = 1; i<v.size(); i++){
        root = insertNode(root, &v[i]); // 알맞은 위치를 찾아 삽입합니다.
    }
    
    preorder(root);
    postorder(root);
    answer.push_back(pre);
    answer.push_back(post);
    
    return answer;
}