길찾기게임 - 이진탐색(전위,후위)

programmers.co.kr/learn/courses/30/lessons/42892

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

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

struct Node{
    int x;
    int y;
    int number;
    Node * left;
    Node * right;
};

bool desc( Node a, Node b)
{
    if(a.y == b.y){
        return a.x<b.x;
    }
    
    return a.y >b.y;
}

void addNode(Node *parent, Node * child)
{
    if(child->x <parent->x){ //왼쪽에 있으면 왼쪽에 넣어주되 이미 child가 있으면 또재귀로 탐색
        if(parent->left == NULL){
            parent->left = child; 
        }
        else{
            addNode(parent->left,child);
        }
    }
    else{
        if(parent->right==NULL){ // 오른쪽도 마찬가지
            parent->right = child;
        }
        else{
            addNode(parent->right,child);
        }
    }
    
}

void preorder(vector<int> & answer, Node * node){ //전위 순회 현재노드-> 왼->오
    if(node == NULL)
        return;
    answer.push_back(node->number);
    preorder(answer,node->left);
    preorder(answer,node->right);
    
}

void postorder(vector<int> &answer, Node *node){ //후위순회 왼->오->현재노드
    if(node==NULL)
        return;
    postorder(answer,node->left);
    postorder(answer,node->right);
    answer.push_back(node->number);

}


vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    
    vector<vector<int>> answer={{},{}};
    vector<Node> node;
    Node * root;
    for(int i=0; i<nodeinfo.size(); i++){
        Node tmp;
        tmp.x = nodeinfo[i][0];
        tmp.y = nodeinfo[i][1];
        tmp.number = i+1;
        node.push_back(tmp);
    }
    sort(node.begin(), node.end(), desc);
    root = &node[0]; //첫번째 노드를 넣어준다. 
    for(int i=1; i<node.size(); i++){
        addNode(root,&node[i]);
    }
    
    preorder(answer[0],root);
    postorder(answer[1],root);
    
    return answer;
}

- 노드를 직접만들어서 이진탐색을 하는 문제이다. 

- 노드를 구조체로 만들고 포인터를 쓰려하니까 낯설고 헷갈린다. 

- 전위 후위순회를 직접 구현하려했을 때 좀 막막했다. 

 

<JAVA>

import java.util.*;
class Solution {
    
    class Node{
        int x;
        int y;
        int num;
        Node left;
        Node right;
        
        Node(int x, int y, int num){
            this.x=x;
            this.y=y;
            this.num = num;
        }
    }
    

    
    public void insert(Node node, Node parent){
        
        if(parent.x<node.x){ //더 오른쪽
            if(parent.right==null) parent.right = node;
            else{
                insert(node,parent.right);
            }
        }
        else{
            if(parent.left==null) parent.left = node;
            else{
                insert(node,parent.left);
            }
        }
        
        
    }
    
    public void preorder(Node node, ArrayList<Integer>arr){
        
        if(node==null){return;}
        
        arr.add(node.num);
        preorder(node.left,arr);
        preorder(node.right,arr);
        
        
    }
    
    
    public void postorder(Node node, ArrayList<Integer>arr){
        
        if(node==null){return;}
        postorder(node.left,arr);
        postorder(node.right,arr);
        arr.add(node.num);
        
    }
    
    
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0;i<nodeinfo.length; i++){
            nodes[i] = new Node(nodeinfo[i][0],nodeinfo[i][1],i+1);
        }
        
        Arrays.sort(nodes, new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b){
                int res = -Integer.compare(new Integer(a.y) , new Integer(b.y));
              //  if(res!=0){
                    return res;
               // }
                
                //return Integer.compare( new Integer(a.x), new Integer(b.y));  -> 왜 x축기준으로 오름차순 정렬하면 런타임 이셉션이나지?
                
            }
        });
        
       Node root = nodes[0];
        
        for(int i=1; i<nodes.length; i++){
          insert(nodes[i],root);
        }
        
        ArrayList<Integer>prearr = new ArrayList<>();
        ArrayList<Integer>postarr = new ArrayList<>();
        
        preorder(root,prearr);
        postorder(root,postarr);
        
        answer[0] = prearr.stream().mapToInt(l->l).toArray();
        answer[1] = postarr.stream().mapToInt(l->l).toArray();        
        
        return answer;
    }
}