길 찾기 게임 - 2019 Kakao Blind Recruitment (Java, Level 3)

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

 

풀이

 노드들을 그래프에 나타내보면 BST의 전체 모습을 알 수 있다. 해당 모습의 BST가 되기 위해서는 루트 노드부터 리프 노드까지 차례대로 해당 노드를 트리에 add해야 한다.(BST의 문제점으로 자료 삽입 순서에 따라 트리의 구조가 바뀌는 점이 있다.)

 

 따라서 nodeInfo에 담긴 노드 정보를 순서에 맞게 정렬해야 한다. 

 

정렬 기준은 첫 번째는 y값이 큰 순서대로, 두 번째는 같은 y값이라면 x값이 작은 순서대로!

 

Node 클래스

static class Node {
    int num;
    int x;
    int y;

    Node parent;
    Node leftChild;
    Node rightChild;

    public Node(int num, int x, int y) {
        this.num = num;
        this.x = x;
        this.y = y;
    }
}

 

 노드 번호, x값, y값을 기본으로 가지며 BST를 구현하기 위해 노드 간의 관계를 정하는 Node 클래스 자료형인 parent, leftChild, rightChild 필드를 추가했다.

 

makeOrderNodeList() 

 node 객체 리스트를 만든 후 위에 언급한 정렬 기준으로 리스틀르 정렬하는 메소드

 

private ArrayList<Node> makeOrderNodeList(int[][] nodeinfo, int nodeCnt) {
    ArrayList<Node> nodeList = new ArrayList<>();
    
    //번호 : index + 1
    for (int i = 0; i < nodeCnt; i++) {
        nodeList.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
    }//for end

    nodeList.sort(new Comparator<Node>() {
        @Override
        public int compare(Node n1, Node n2) {
            //1. y좌표 큰 순서대로
            int result = Integer.compare(n2.y, n1.y);

            //2. y좌표 같다면 x좌표 작은 순서대로
            if (result==0) {
                return Integer.compare(n1.x, n2.x);
            }//if end

            return result;
        }
    });

    return nodeList;
}

 

//in solution()
ArrayList<Node> nodeList = makeOrderNodeList(nodeinfo, nodeCnt);

 

 

 

BST에 넣을 순서대로 정렬한 리스트를 만들었으니 이제 BST에 node를 추가한다. BST를 만든다는 것은 node 객체들끼리 관계를 맺어주는 것이라 생각하면 된다. 

 

 일단, BST의 root node는 리스트의 첫 번째 요소가 된다. root node를 시작으로 리스트 순서대로 node간 관계를 맺어준다. 여기서 BST의 기준은 node의 x좌표다. 자신의 x좌표가 부모 노드의 x좌표보다 크다면 부모 노드의 오른쪽으로 이동을 하는데, 만일 부모 노드의 rightChild가 null이면 본인이 rightChild가 될 것이고, null이 아니라면 해당 rightChild를 부모로하여 다시 재귀적으로 탐색하면 된다.

 

addNode()

private void addNode(Node parent, Node node) {
    int parentX = parent.x;
    int nodeX = node.x;

    if (parentX<nodeX) {
        if (parent.rightChild==null) {
            node.parent = parent;
            parent.rightChild = node;
        } else {
            addNode(parent.rightChild, node);
        }//if~else end
    } else {
        if (parent.leftChild==null) {
            node.parent = parent;
            parent.leftChild = node;
        } else {
            addNode(parent.leftChild, node);
        }//if~else end
    }//if~else end
}//addNode() end

 

//in solution()
int nodeCnt = nodeinfo.length;

Node root = nodeList.get(0);

for (int i = 1; i < nodeCnt; i++) {
    addNode(root, nodeList.get(i));
}//for

 

 

 이제 BST가 만들어졌으니 preorder, postorder traversal하면 된다.

 preorder traversal은 부모 방문 -> left subtree 이동 -> right subtree 이동 순서이고,

 postorder traversal은 left subtree 이동 -> right subtree 이동 -> 부모 방문 순서이므로, 해당 순서에 맞게 각각 재귀 메소드를 만든다.

 

preOrder()

private void preOrder(Node parent, ArrayList<Integer> result, int nodeCnt) {
    if (parent==null) {
        return;
    }//if end

    result.add(parent.num); //부모 방문
    preOrder(parent.leftChild, result, nodeCnt); //left subtree 이동
    preOrder(parent.rightChild, result, nodeCnt); //right subtree 이동
}//preOrder() end

postOrder()

private void postOrder(Node parent, ArrayList<Integer> result, int nodeCnt) {
    if (parent==null) {
        return;
    }//if end

    postOrder(parent.leftChild, result, nodeCnt); //left subtree 이동
    postOrder(parent.rightChild, result, nodeCnt); //right subtree 이동
    result.add(parent.num); //부모 방문
}//postOrder() end

 

//in solution()

//순회 결과값 담을 list
ArrayList<Integer> preOrderList = new ArrayList<>();
ArrayList<Integer> postOrderList = new ArrayList<>();

//전위 후위 순회
preOrder(root, preOrderList, nodeCnt);
postOrder(root, postOrderList, nodeCnt);

//list -> array
int[] preOrderResult = preOrderList.stream()
                                    .mapToInt(Integer::intValue)
                                    .toArray();

int[] postOrderResult = postOrderList.stream()
                                        .mapToInt(Integer::intValue)
                                        .toArray();

int[][] answer = new int[2][];
answer[0] = preOrderResult;
answer[1] = postOrderResult;

return answer;