Programmers - 길 찾기 게임 with JAVA (V)

 

 

기본 개념

-> 기본적으로 루트노드의 위치에 따라 중위, 전위, 후위 순회이다. 왼쪽, 오른쪽은 고정

 

 

1. 중위 순회 (inorder) : 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순으로 방문

(가장 루트 노드에서 시작해 더이상 왼쪽 서브트리가 없을때 해당 노드를 방문처리 -> 그 노드의 루트 노드 -> 오른쪽 서브 트리 동일 처리)

 

방문 순서 : F -> B -> A(방문) -> B(방문) -> D -> C(방문) -> D(방문) -> E(방문) -> F(방문) -> G(방문) -> I -> H(방문) -> I(방문)

결과 : A - B - C - D - E - F - G -H - I

 

 

 

 

2. 전위 순회 (preorder) : 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

 

방문 순서 : F(방문) -> B(방문) -> A(방문) -> B ->  D(방문) -> C(방문) -> D ->  E(방문) ->  D -> B -> F -> G(방문)

 -> I(방문) -> H(방문)

결과 : F - B - A - D - C - E - G - I - H

 

 

 

 

 

3.  후위 순회 (postorder) : 왼쪽 서브 트리 - 오른쪽 서브 트리 - 루트 노드

 

 

방문 순서 : F -> B -> A(방문) -> B -> D -> C(방문) -> D -> E(방문) -> D(방문) -> B(방문) -> F -> G -> I -> H(방문) -> I(방문)

-> G(방문) -> F(방문)

결과 : A - C - E - D - B - H - I - G - F

 

 

 

 

로직

1. 노드 생성

2. 노드 정렬 : compareTo 구현

3. 노드간 연결 : 재귀함수로 구현

4. 전위 순회 : 재귀함수로 구현

5. 후위 순회 : 재귀함수로 구현

 

 

 

코드

import java.util.*;
class Solution {
    static int[][] answer;
    static int index;
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        // 노드 생성
        List<Node> nodes = new ArrayList<>();
        for(int i=0; i<nodeinfo.length; i++){
            nodes.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        Collections.sort(nodes);
        Node parent = nodes.get(0);
        
        // 트리 생성 - 루트 노드를 계속 보내서 생성
        for(int i=1; i<nodes.size(); i++){
            makeTree(parent, nodes.get(i));
        }
        
        // 전위 순회
        index = 0;
        preorder(parent);
        
        // 후위 순회
        index = 0;
        postorder(parent);
        return answer;
    }
    
    // 전위 순회 - 현재 노드가 null이라면 그냥 반환 따라서, root-left-right 순이 됨.
    static void preorder(Node parent){
        if(parent != null){
            answer[0][index] = parent.num;
            index += 1;
            preorder(parent.left);
            preorder(parent.right);   
        }
    }
    
    // 후위 순회 - 현재 노드가 null이라면 그냥 반환 따라서, left-right-root 순이 됨.
    static void postorder(Node parent){
        if(parent != null){
            postorder(parent.left);
            postorder(parent.right);
            answer[1][index] = parent.num;
            index += 1;   
        }
    }
    
    // 트리 생성
    static void makeTree(Node parent, Node child){
        if(parent.x > child.x){
            if(parent.left == null){
                parent.left = child;
            }
            else{
                makeTree(parent.left, child);
            }
        }
        else{
            if(parent.right == null){
                parent.right = child;
            }
            else{
                makeTree(parent.right, child);
            }
        }
    }
    
    // 노드 클래스
    static class Node implements Comparable<Node>{
        public int num;
        public int x;
        public int y;
        public Node left;
        public Node right;
        
        public Node (int num, int x, int y){
            this.num = num;
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Node n){
            if(this.y == n.y){
                return n.x-this.x;
            }
            return n.y-this.y;
        }
    }
}