[Lv.3] 길 찾기 게임

import java.util.*;

class Solution {
    static List<Integer> preResult=new ArrayList<>();
    static List<Integer> postResult=new ArrayList<>();
    static List<Point> pointList=new ArrayList<>();
    public int[][] solution(int[][] nodeinfo) {

        for (int i = 0; i < nodeinfo.length; i++) {
            int[] ints = nodeinfo[i];
            pointList.add(new Point(ints[0], ints[1], i + 1));
        }
        Collections.sort(pointList);
        Point root= pointList.get(0);
        for (int i = 1; i < pointList.size(); i++) {
            insertPoint(root,pointList.get(i));
        }
        preOrder(root);
        postOrder(root);
        int[] ints = preResult.stream().mapToInt(i -> i).toArray();
        int[] ints1 = postResult.stream().mapToInt(i -> i).toArray();
        return new int[][]{ints,ints1};
    }
    public void preOrder(Point point){
        preResult.add(point.indexValue);
        if(point.left!=null){
            preOrder(point.left);
        }
        if(point.right!=null){
            preOrder(point.right);
        }
    }
    public void postOrder(Point point){
        if(point.left!=null){
            postOrder(point.left);
        }
        if(point.right!=null){
            postOrder(point.right);
        }
        postResult.add(point.indexValue);
    }
    public void insertPoint(Point parent, Point child){
        if(parent.x> child.x){
            if(parent.left==null){
                parent.left=child;
                child.parent=parent;
            }else
                insertPoint(parent.left,child);
        }else{
            if(parent.right==null){
                parent.right=child;
                child.parent=parent;
            }else insertPoint(parent.right,child);
        }
    }

    class Point implements Comparable<Point>{
        int x,y;
        int indexValue;
        Point parent;
        Point left,right;

        public Point(int x, int y, int indexValue) {
            this.x = x;
            this.y = y;
            this.indexValue = indexValue;
        }

        @Override
        public int compareTo(Point o) {
            if(this.y==o.y)
                return this.x-o.x;
            return o.y-this.y;
        }
    }
}

---

이진 트리만 만들면 그것도 삽입 기능만 있는 이진트리만 만들면 되는 문제다.

처음엔, 이진 트리를 직접 만들기 싫어 다른 방법 (레벨별로 맵을 만들어 해당 레벨에서 탐색을 시도하는..)을 시도했으나 복잡하게 꼬이기만하고 정리될 기미가 보이지 않았다.

그래서, 그냥 이진 트리를 직접 만들었다..!

로직은 단순하다.

입력된 점들을 받아 정렬하고 그걸 바탕으로 상위 노드부터 부모 자식관계를 설정하면된다.

부모보다 x값이 작다면 왼쪽에 위치하고 이때 부모가 왼쪽 자식이 있다면 해당 자식을 다시 부모로 여겨 똑같은 로직을 돈다.

마찬가지로 오른쪽도 x값이 부모보다 크면 부모의 오른쪽 서브트리로 가고 부모가 오른쪽 자식이 있다면 해당 자식을 다시 부모로 여긴다.

(코드에선 자식의 부모도 설정했는데 사실 이 문제에선 필요없다.)

 

이렇게 이진 트리를 구현하고 전위, 후위 순회를 하면 가볍게 정답을 맞출 수 있다.

 

전위 순회의 경우 Root->Left->Right순으로 트리를 탐색하는 순회이고 코드를 보면 이해하기 쉬울 것이다.

후위 순회의 경우 Left->Right->Root순으로 트리를 탐색하는 탐색하는 순회이고 마찬가지로 코드를 보면 이해될 것이다.

 

이번 문제는 사실 이진트리만 구현할 줄 알면 쉽게 풀 수 있는 문제였다.

근데, 자료구조 강의를 들은지 한참 되기도 했고.. 막상 구현하려니 쉽게 빠박 하고 코드를 써내려가질 못했다.

그래서 다른 방법을 시도해보았고 꽤 오래 시도했지만 이진트리를 만드는게 문제의 취지에도 맞고 코드 가독성도 훨씬 좋을 것이라 생각이 되어 이진트리를 구현하여 푼 문제다..