[Programmers]LV3 - 길 찾기 게임

https://programmers.co.kr/learn/courses/30/lessons/42892

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

 

 

 

문제 파악

 

문제에 주어진 설명에서 간선, 전위 순회, 후위 순회를 보고서 트리 구조로 문제를 풀어야겠다는 생각이 들었다.

왜냐하면, X좌표를 기준으로 BST가 만들수 있겠다는 판단이 섰기 때문이다.

 

그런데 이론만 알고 막상 트리를 구현하려고 하니 생각보다 잘 안돼서 트리 구조에 대해 다시 공부하고 풀었다..

모르는 걸 새로 알아가는 것도 좋지만 이런 걸 모르면 좀...상태가 심하다는 생각이 들었다.. 공부 열심히 해야지

 

import java.util.*;
class Solution {
    static int[][] result;
    static int num = 0;
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = {};
        result = new int[2][nodeinfo.length];
        
        ArrayList<Node> list = new ArrayList<>();
        
        for(int idx = 0; idx<nodeinfo.length;idx++)
        {
            list.add(new Node(nodeinfo[idx][0],nodeinfo[idx][1],idx+1,null,null));
        }
        
        Collections.sort(list, new Comparator<Node>(){
           public int compare(Node n1, Node n2){
               if(n1.y == n2.y){
                   return n1.x-n2.x;
               }
               else{
                   return n2.y-n1.y;
               }
           } 
        });
   
        Node root = list.get(0);
        for(int idx = 1; idx<list.size();idx++)
        {
            insert(root,list.get(idx));
        }
        
        preorder(root);
        num = 0;
        postorder(root);
        
        return result;
    }
    
    public void insert(Node root,Node child)
    {
        if(root.x > child.x){
            if(root.left == null) root.left = child;
            else insert(root.left,child);
        } else {
            if(root.right == null) root.right = child;
            else insert(root.right,child);
        }
    }
    public void preorder(Node root){
        if(root == null) return;      
        
        result[0][num++] = root.index;
        
        preorder(root.left);
        preorder(root.right);        
    }
    public void postorder(Node root)
    {
        if(root == null) return;
        
        postorder(root.left);
        postorder(root.right);
        
        result[1][num++] = root.index;
    }
}
class Node
{
    int x;
    int y;
    int index;
    Node left;
    Node right;
    
    Node(int x, int y, int index,Node left, Node right)
    {
        this.x = x;
        this.y = y;
        this.index = index;
        this.left = left;
        this.right = right;
    }
}