[ 프로그래머스 ] #42892 : 길 찾기 게임 - JAVA

🔗 길 찾기 게임

import java.util.*;
class Solution {
    private static 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;
        }
    }

    private static Node makeTree(int [][] nodeinfo){
        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);
        }

        // y기준으로 내림차순 정렬, y가 같다면 x 를 기준으로 오름차순 정렬
        Arrays.sort(nodes, (o1,o2)->{
            if(o1.y==o2.y)return Integer.compare(o1.x,o2.x);
            return Integer.compare(o2.y,o1.y);

        });

        Node root=nodes[0];

        for(int i=1;i<nodes.length;i++){
            Node parent=root;
            while(true){
                // 부모 노드의 x좌표가 더 크면 
                if(nodes[i].x <parent.x){
                    if(parent.left==null){
                        // 다음 노드를 부모의 left 로 함 
                        parent.left=nodes[i];
                        break;
                    }
                    else{
                        // 왼쪽 자식을 부모로해서 탐색할 수 있도록 
                        parent=parent.left;
                    }
                }else{ // 부모 노드의 x 좌표가 작다면
                    if(parent.right==null){
                        // 노드를 부모의 right로 함
                        parent.right=nodes[i];
                        break;
                    }else{
                        // 오른쪽 자식을 부모로 해서 탐색할 수 있도록 
                        parent=parent.right;
                    }
                }
            }
        }
        return nodes[0];
    }

    private static void preOrder(Node curr, ArrayList<Integer>answer){
        if(curr==null)return ;
        answer.add(curr.num);
        preOrder(curr.left,answer);
        preOrder(curr.right,answer);
    }

    private static void postOrder(Node curr, ArrayList<Integer> answer){
        if(curr==null)return;
        postOrder(curr.left,answer);
        postOrder(curr.right,answer);
        answer.add(curr.num);

    }
    public int[][] solution(int[][] nodeinfo) {
        // nodeinfo : 이진트리를 구성하는 노드들의 좌표가 담긴 배열
        // i+1번 노드의 {x,y}

        // 이진트리를 전위 순회, 후위 순회한 결과를 순서대로 담아 return 

        Node root=makeTree(nodeinfo); // 이진 트리 생성
        ArrayList<Integer> preOrderList=new ArrayList<>();
        preOrder(root,preOrderList);
        ArrayList<Integer> postOrderList=new ArrayList<>();
        postOrder(root,postOrderList);

        int[][] answer=new int[2][nodeinfo.length];
        answer[0]=preOrderList.stream().mapToInt(Integer::intValue).toArray();
        answer[1]=postOrderList.stream().mapToInt(Integer::intValue).toArray();

        return answer;
    }
}