[프로그래머스,Java] Level3: 길찾기 게임

 

문제분석:

 

문제 목표: x값, y값을 주어지는 노드들을   이진트리로 구성한뒤, 전위순회, 후위순회를 한 결과를 출력하세요.

 

 

이 문제의 출제의도는   이진트리를 구현하고  전위,후위 순회를 할 수 있는지를 물어보고있다.

 

 

처음에 이 문제가 DFS문제인가 싶어서 풀기시작했다가  이상함을 느꼇다.

 

당연하다면 당연하다..  이진트리의 탐색 조건과  DFS/BFS의 완전탐색은  다른 로직이기때문이다.

 

 

이진트리를 써보기나했지(Heap), 구현해 본적이 없어서이다..

 

그래서 이진트리 만드는법 문서를 참고를했다.

 

 

1. Node 생성하기 

 

이진트리를 만드려면  Node가 필요하다.  그 Node 하나엔 노드번호, x좌표,y좌표, 오른쪽 자식노드 ,왼쪽 자식노드 의 

정보가 꼭 필요하니 객체를 하나 생성해준다.

 

2. Node정보 입력 및 정렬

 

 

Node 정보를 입력해주는 반복문을 1개 작성한다.

 

그 후, Node들을 정렬을 해야한다.

 

정렬을 하는이유는, 입력으로 주어지는 노드들이 무작위로 배치가 되어있기에  

이진트리를 만들기위해서  정렬을 해야한다.

 

우선, Level(y값)을 기준으로 1차 정렬을 해줘야한다. 

만약 Level이같다면  x값이 작은순부터(오름차순)으로 정렬을해야한다.

 

3.이진 트리 작성

 

 

이진트리를 작성하자!

 

최 상단 부모노드를 찾은뒤,

이진트리 작성 로직은  MakeTree[ 부모 , 넣을 노드] 를 이용한다. 

 

MakeTree는  부모의 x값보다 작으면 왼쪽 자식노드에, x값보다 크면 오른쪽 자식노드에 넣는다.

 

만약, 부모에 자식노드에 이미 값이 존재한다면, MakeTree [부모의 자식노드, 넣을노드] 로 다음 Level 작업으로 진행한다.

 

이렇게하면 트리가 작성이된다.

 

4. 전위순회, 후위순회 실시

 

 

전위, 후위순회 알고리즘은 은근 간단했다.

 

전위순회는 탐색순서가  루트노드 -> 왼쪽자식 -> 오른쪽 자식 순서대로인데 

그 논리대로  루트(출력) -> 왼쪽 자식노드 -> 오른쪽자식노드로 입력한다.

 

후위순회 탐색순서는  왼쪽 자식노드-> 오른쪽자식노드 -> 루트노드 순서대로 

작성하자.

 

문제풀이:

import java.util.*;
class Node {
    
    public int value;
    public int x;
    public int y;
    public Node right;
    public Node left;
    
    public Node (int value,int x, int y, Node right, Node left){
        this.value= value;
        this.x = x;
        this.y = y;
        this.right = right;
        this.left =left;
    }
    
}
 
class Solution {
    
int[][] result;
int idx =0;
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = {};
        
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0;i<nodeinfo.length;i++){
            nodes[i]=new Node(i+1,nodeinfo[i][0],nodeinfo[i][1],null,null);
        }
        
        //정렬규칙 Y는 내림차 X는 오름차순
        Arrays.sort(nodes,new Comparator<Node>(){
            public int compare(Node a , Node b){
                if(a.y==b.y){
                    return a.x-b.x;
                }
                return b.y-a.y;
            }
        } );
        
        Node parent = nodes[0];
        
        for(int i=1;i<nodes.length;i++){
            MakeTree(parent,nodes[i]);
        }
        
        
        result= new int[2][nodeinfo.length];
        
        
        preorder(parent);
        idx=0;
        postorder(parent);
        
        return answer=result;
    }
    
    public void MakeTree (Node parent, Node child){
      if(parent.x<child.x){      
        if(parent.right==null){
            parent.right=child;
        }
         else{
            MakeTree(parent.right,child);
         }
      }
      else{
        if(parent.left==null){
            parent.left=child;
        }
        else{
            MakeTree(parent.left,child);
        }
      }  
        
    }
    
    public void preorder(Node root){
        if(root!=null){
            result[0][idx++]=root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root){
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            result[1][idx++] = root.value;
        }
    }
}