길 찾기 게임

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

import java.util.*;
class Solution {
    class Node{
        int x;
        int y;
        int idx;
        Node left;
        Node right;
        Node (int x, int y, int idx){
            this.x = x;
            this.y = y;
            this.idx = idx;
        }
    };
    Comparator<Node> comp = new Comparator<Node>(){
        public int compare(Node a, Node b){
            if(a.y < b.y) return 1;
            else if (a.y > b.y) return -1;
            else {
                return a.x - b.x;
            }
        }  
    };
    
    void addNode(Node parent, Node child){
        if(child.x < parent.x){
            if(parent.left == null) {
                parent.left = child;
                return;   
            }else addNode(parent.left, child);
        }else if(child.x > parent.x){
            if(parent.right == null){
              parent.right = child;
              return;
            }else addNode(parent.right, child);
        }
    }
    int idx = 0;
    void preorder(Node node, int[][] answer){
        if(node == null) return;
        answer[0][idx++] = node.idx;
        preorder(node.left,answer);
        preorder(node.right,answer);
    }
    void postorder(Node node, int[][] answer){
        if(node == null) return;
        postorder(node.left,answer);
        postorder(node.right,answer);
        answer[1][idx++] = node.idx;
    }
    public int[][] solution(int[][] nodeinfo) {
        int nodeLength = nodeinfo.length;
        int[][] answer = new int[2][nodeLength];
        List<Node> nodes = new LinkedList<Node>();
        
        for(int i = 0 ; i < nodeLength; i++){
            nodes.add(new Node(nodeinfo[i][0],nodeinfo[i][1],i+1));
        }
        nodes.sort(comp);
        Node root = nodes.get(0);
        
        for(int i = 1; i < nodeLength; i++){
            addNode(root, nodes.get(i));
        }
        preorder(root,answer);
        idx = 0;
        postorder(root,answer);
        return answer;
    }
}

• 서술 : Node를 만들어 리스트에 담고, 미리 정렬해놓는다. (y가 높은순, y가 같다면 x가 작은순) Node객체의 left, right를 모두 설정해놓고, 전위순회, 후위순회를 하며 answer 배열에 idx를 순서대로 담는다.
• 이진를 위한 좌표가 주어졌을때 구현을 하는것이 포인트. + 전위순회, 후위순회