[프로그래머스] 길 찾기 게임

풀이)

이진탐색트리를 구현하면 되는 문제이다.

풀이과정은 이러하다.

1. 각 node의 번호를 좌표 옆에 삽입시켜 준다. (탐색 시 노드 번호를 출력하기 위해서)

2. 각 node들을 좌표순으로 정렬해준다. 

    (원래 이진탐색트리는 삽입 순서에 따라 트리모양이 달라지지만, 이 문제에서는 

     (x,y)좌표 순으로 노드들이 이진트리를 구성하기 때문에 삽입순서가 중요하지 않다.

좌표가 중요하다.

     y좌표가 높은 순, y좌표가 같다면 x좌표가 작은 순으로 나열한다.)

3. 각 노드들로 이진탐색트리를 만들어 순회 경로를 출력한다.

   전위순회는 나 자신 -> 왼쪽자식 ->오른쪽 자식 순이고

   후위순회는 왼쪽자식 ->오른쪽자식 ->나 자신 순이다.

코드)

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

struct node{
    int x,y,idx; //좌표, 노드 번호
    node *left; //왼쪽자식
    node *right; //오른쪽자식
    //생성자
    node(int x,int y,int idx){
        this->x = x;
        this->y = y;
        this->idx = idx;
        left = NULL;
        right = NULL;
    }
};
class binarysearch_tree{
    public:
    node *root;
    vector<vector<int>> answer={{},{}};
    //생성자
    binary_tree(vector<vector<int>> nodeinfo){
        node *r = new node(nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2]);
        this->root = r;//root설정
        for(int i=1;i<nodeinfo.size();i++){//자식들 삽입
             node *temp = new node(nodeinfo[i][0], nodeinfo[i][1], nodeinfo[i][2]);
            insert(this->root, temp);
            //cout <<"삽입완료" << endl;
        }

        //순회저장
        preorder(this->root);
        postorder(this->root);
    }
    //전위순회 answer[0]에저장
    void preorder(node *root){
        this->answer[0].push_back(root->idx);
        if(root->left) preorder(root->left);
        if(root->right) preorder(root->right);
    }

    //후위순회 answer[1]에 저장
    void postorder(node *root){
        if(root->left) postorder(root->left);
        if(root->right) postorder(root->right);
        this->answer[1].push_back(root->idx);
    }
    private:
    void insert(node *root, node *temp){

        if(root->x < temp->x){//node의 x좌표값이 root의 x좌표보다 크면 오른쪽 자식
            if(root->right == NULL) root->right = temp; 
            else{
                insert(root->right,temp);
            }
        }
        else{//node의 x좌표값이 root의 x좌표보다 작으면
            if(root->left == NULL) root->left = temp;
            else{
                insert(root->left,temp);
            }
        }
    }
};
bool cmp(const vector<int> &a, const vector<int> &b){
    if(a[1] == b[1]) return a[0] < b[0];
    else return a[1] > b[1];
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    for(int i=0;i<nodeinfo.size();i++){
        nodeinfo[i].push_back(i+1) ; //나중에 출력위해서 노드 번호 삽입
    }
    //y축좌표 높은순, x축좌표적은순
    sort(nodeinfo.begin(),nodeinfo.end(),cmp);
    binarysearch_tree bt(nodeinfo);

    return bt.answer;
}