[프로그래머스] 길 찾기 게임 (Java)

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

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

import java.util.*;

class Solution {
    static class Node implements Comparable<Node>{
        int num, y, x;
        Node left, right;
        public Node(int num, int y, int x, Node left, Node right){
            this.num=num;
            this.y=y;
            this.x=x;
            this.left=left;
            this.right=right;
        }
        @Override
        public int compareTo(Node o){
            if (o.y==this.y){
                return this.x-o.x;
            }
            return o.y-this.y;
        }
    }
    static int pre_cnt=0;
    static int post_cnt=0;
    static int[][] answer;
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        Node[] nodes=new Node[nodeinfo.length];
        for (int i=0; i<nodeinfo.length; i++){
            nodes[i]=new Node(i+1, nodeinfo[i][1], nodeinfo[i][0], null, null);
        }
        Arrays.sort(nodes);
        Node root=nodes[0]; 
        for (int i=1; i<nodeinfo.length; i++){
            tree(nodes[0], nodes[i]);
        }
        preorder(root);
        postorder(root);
        return answer;
    }
    
    public void preorder(Node node){
        answer[0][pre_cnt++]=node.num;
        if (node.left!=null) preorder(node.left);
        if (node.right!=null) preorder(node.right);
    }
    
    public void postorder(Node node){
        if (node.left!=null) postorder(node.left);
        if (node.right!=null) postorder(node.right);
        answer[1][post_cnt++]=node.num;
    }
    
    public void tree(Node parent, Node child){
        if (parent.x<child.x){
            if (parent.right==null) parent.right=child;
            else tree(parent.right, child);
        }
        else{
            if (parent.left==null) parent.left=child;
            else tree(parent.left, child);
        }
    }
}

자료구조 기본기를 보는 듯한 문제.. 이진트리의 구조에 대해 파악하고 있어야 한다.

각 노드의 자식은 재귀로 구한다. root와 비교해서, x가 작으면 root의 왼쪽 subtree로, root의 왼쪽 subtree보다 x가 크면 root의 왼쪽 subtree의 오른쪽 subtree로... 이런 식으로 parent.left, parent.right 가 Null일 때까지 반복해준다.. 

처음엔 이 개념이 생각나지 않아 고민을 많이 했다.