길 찾기 게임

import java.util.*;
class Solution {
    public static void Connect(Node parent, Node child) {
        if (parent.x > child.x) {
            if (parent.left == null) {
                parent.left = child;
            } else {
                Connect(parent.left, child);
            }
        } else {
            if (parent.right == null) {
                parent.right = child;
            } else {
                Connect(parent.right, child);
            }
        }
    }
 
    public static void preOrder(Node node, ArrayList<Integer> order) {
        if (node == null)
            return;
        order.add(node.data);
        preOrder(node.left, order);
        preOrder(node.right, order);
    }
 
    public static void postOrder(Node node, ArrayList<Integer> order) {
        if (node == null)
            return;
        postOrder(node.left, order);
        postOrder(node.right, order);
        order.add(node.data);
    }
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][];
        // 노드 초기화
        ArrayList<Node> list = new ArrayList<Node>();
        for (int i = 0; i < nodeinfo.length; i++) {
            list.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }
 
        // y 내림차순 정렬
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.y - o1.y;
            }
        });
 
        Node root = list.get(0);
        // 노드 연결
        for (int i = 1; i < list.size(); i++) {
            Connect(root, list.get(i));
        }
 
        // 순회 저장
        ArrayList<Integer> order = new ArrayList<Integer>();
        preOrder(root, order);
        answer[0] = order.stream().mapToInt(Integer::intValue).toArray();
        order.clear();
        postOrder(root, order);
        answer[1] = order.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}
class Node {
    int data;
    int x, y;
    Node left, right;
 
    Node(int data, int x, int y) {
        this.data = data;
        this.x = x;
        this.y = y;
    }
}

노드를 연결하는 과정이 어려웠다.

하지만 단순하게 생각하여 루트부터 자식노드 끝까지 타고 내려간 후 삽입하면 된다.

 

참고 사이트 : https://minhamina.tistory.com/107