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

참고 : programmers.co.kr/learn/courses/30/lessons/42892

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

 

- 트리 순회 

- y좌표가 가장 큰 값 -> 루트 노드

- y좌표가 같다 = 같은 레벨에 있는 노드

- y좌표가 같고 x좌표가 적다 -> 왼쪽 자식 노드일 가능성이 있다.

- y좌표가 같고 x좌표가 크다 -> 오른쪽 자식 노드일 가능성이 있다.

- 이후 트리 구성 후 전위 순회, 후위 순회를 재귀로 돌아주고 각 순서를 answer에 넣어준다.

 

import java.util.*;

class Solution {
    
    int index = 0;
    
    private void insertNode(Node rootNode, Node childNode) {
        if (rootNode.x > childNode.x) {
            if(rootNode.left != null) {
                insertNode(rootNode.left, childNode);
            } else {
                rootNode.left = childNode;   
            }
        } else {
            if(rootNode.right != null) {
                insertNode(rootNode.right, childNode);
            } else {
                rootNode.right = childNode;
            }
        }
    }
    
    private void preOrder(int[][] arr, Node node) {
        if(node != null) {
            arr[0][index++] = node.idx;
            if(node.left != null) {
                preOrder(arr, node.left);
            }
            if(node.right != null) {
                preOrder(arr, node.right);
            }
        }
    }
    
    private void postOrder(int[][] arr, Node node) {
        if(node != null) {
            if(node.left != null) {
                postOrder(arr, node.left);
            }
            if(node.right != null) {
                postOrder(arr, node.right);
            }
            arr[1][index++] = node.idx;
        }
    }
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        Node[] nodes = new Node[nodeinfo.length];
        for(int i=0; i<nodeinfo.length; i++) {
            nodes[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i+1);
        }
        Arrays.sort(nodes, new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                if(n2.y == n1.y) {
                    return n1.x - n2.x;
                }
                return n2.y - n1.y;
            }
        });
        
        Node rootNode = nodes[0];
        
        for(int i= 1; i<nodes.length; i++) {
            insertNode(rootNode, nodes[i]);
        }
        
        preOrder(answer, rootNode);
        index = 0;
        postOrder(answer, rootNode);
        
        return answer;
    }
}

class Node {
    int x;
    int y;
    int idx;
    Node left = null;
    Node right = null;
   public Node(int x, int y, int idx) {
       this.x = x;
       this.y = y;
       this.idx = idx;
   }
    
}