[Programmers] 길 찾기 게임

이진트리의 순회 문제이다.

이 문제는 이진트리의 노드들이 주어지고 전위순회(루트->좌->우), 후위순회(좌->우->루트)를 구하는 문제였다. 보통의 문제들과 다른점은 간선을 그리는 것이 주요한 문제였다. 따라서 두가지 과정을 거쳐 간선을 그려보았다. 일단 첫번째로 모든 노드들을 y로 내림차순, y가 같다며 x로 오름차순이 되도록 정렬을 하였다. 그 후에 Node라는 클래스를 만들어 left, right를 Node의 형으로 멤버변수(포인터의 개념)를 주고, 정렬된 노드들을 x값을 비교하여 left,right에 할당하며 연결해주었다. 이것을 완료한 후에는 재귀를 이용하여 간단하게 전위순회, 후위순회를 하여 풀었다.

문제의 우선순위, 즉 이문제에서는 간선을 그리는것이 최우선목표인데 그것을 해결하는 것이 중요한 문제였다.

package programmers;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_2019카카오_길찾기게임 {
    
    static StringBuilder preOrderResult;
    static StringBuilder postOrderResult;
    
    static class Node implements Comparable<Node>{
        int num,x,y;
        Node left,right;
        Node(int num,int x,int y){
            this.num=num; this.x=x;this.y=y; left=null; right=null;
        }
        @Override
        public int compareTo(Node o) {
            if(y==o.y) {
                return Integer.compare(x, o.x);    //x에 대하여 오름차순
            }
            return -Integer.compare(y, o.y);    //y에 대하여 내림차순
        }
    }
    
    public static void main(String[] args) {
        int[][] nodeinfo = {{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}};
        int[][] answer=  solution(nodeinfo);
        
        for(int [] a : answer) {
            System.out.println(Arrays.toString(a));
        }
    }
    
    static int[][] solution(int[][] nodeinfo){
        int[][] answer=new int[2][nodeinfo.length];
        
        List<Node> nodes= new ArrayList<>();
        
        
        for(int i=0;i<nodeinfo.length;i++) {
            int x= nodeinfo[i][0];
            int y= nodeinfo[i][1];
            nodes.add(new Node(i+1, x, y));
        }
        
        Collections.sort(nodes);
 
        //간선 연결
        for(int i=1;i<nodeinfo.length;i++) {
            Node root = nodes.get(0);
            
            Node cur= nodes.get(i);
            
            while(true) {
                if(cur.x<root.x) {
                    if(root.left==null) {
                        root.left=cur;
                        break;
                    }
                    root=root.left;
                }else if(root.x<cur.x) {
                    if(root.right==null) {
                        root.right=cur;
                        break;
                    }
                    root=root.right;
                }
            }
        }
        
        Node root= nodes.get(0);
        
        StringTokenizer st = null;
        
        preOrderResult=new StringBuilder();
        preOrder(root);
        st =new StringTokenizer(preOrderResult.toString());
        for(int i=0;i<nodeinfo.length;i++) {
            answer[0][i]=Integer.parseInt(st.nextToken());
        }
        
        
        postOrderResult=new StringBuilder();
        postOrder(root);
        st =new StringTokenizer(postOrderResult.toString());
        for(int i=0;i<nodeinfo.length;i++) {
            answer[1][i]=Integer.parseInt(st.nextToken());
        }
        return answer;
    }
    
    static void preOrder(Node root) {
        preOrderResult.append(root.num+" ");
        if(root.left!=null) {
            preOrder(root.left);
        }
        if(root.right!=null) {
            preOrder(root.right);
        }
    }
    
    static void postOrder(Node root) {
        if(root.left!=null) {
            postOrder(root.left);
        }
        if(root.right!=null) {
            postOrder(root.right);
        }
        postOrderResult.append(root.num+" ");
    }
    
}