[2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임(Java, 간단한 코드)

## 접근

---

1. 주어진 노드의 x, y 좌표를 자료구조에 넣고 정렬한다. y는 내림차순으로, x는 오름차순으로 정렬한다. 정렬의 이유는 트리에 삽입하기 위해서다.

 

 

 

2. 루트 노드에서부터 시작하여, 노드를 넣기 위한 위치를 탐색한다. 노드의 x좌표를 기준으로, 작으면 왼쪽, 크면 오른쪽으로 탐색하다가, null을 만나면 삽입한다.

 

 

 

3. 전위순회와, 후위순회 코드를 작성할 때, 출력 부분을 이용해서 정답을 만든다.

 

 

 

 

##  해설코드(Java).

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
class Solution {
    int[][] answer;
    int preidx = 0;
    int postidx = 0;
        
    class Item{
        int idx, x, y;
        Item(int idx, int x, int y){
            this.idx = idx;
            this.x = x;
            this.y = y;
        }
    }
    
    class Node{
        int num, x, y;
        Node left = null;
        Node right = null;
        Node parent = null;
        
        Node(int num, int x, int y){
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }
    
    class Tree{
        Node root = null;
        
        void addNode(Node newNode){
            if(root == null)
                root = newNode;
            else{
                Node tNode = root;
                while(true){
                    if(tNode.x > newNode.x){
                        // Left  
                        if(tNode.left == null){
                            tNode.left = newNode;
                            newNode.parent = tNode;
                            break;
                        }else
                            tNode = tNode.left;
                    }else if(tNode.x < newNode.x){
                        // Right
                        if(tNode.right == null){
                            tNode.right = newNode;
                            newNode.parent = tNode;
                            break;
                        }else
                            tNode = tNode.right;
                    }
                }
            }
        }
        
        void pre(Node node){
            if(node == null)
                return;
            
            answer[0][preidx++] = node.num;
            pre(node.left);
            pre(node.right);
        }
        
        void post(Node node){
            if(node == null)
                return;
            
            post(node.left);
            post(node.right);
            answer[1][postidx++] = node.num;
        }
    }
    
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        ArrayList<Item> aList = new ArrayList<>();
        Tree tree = new Tree();
        
        for(int i = 0; i < nodeinfo.length; i++){
            aList.add(new Item(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        
        Collections.sort(aList, new Comparator<Item>() {
            @Override
            public int compare(Item i1, Item i2) {
                if(i1.y == i2.y){
                    return Integer.compare(i1.x, i2.x);
                }else
                    return Integer.compare(i2.y, i1.y);
            }
        });
        
        for(Item item : aList){
            tree.addNode(new Node(item.idx, item.x, item.y));
        }
        
        tree.pre(tree.root);
        tree.post(tree.root);
        return answer;
    }
}