programmers. 길 찾기 게임

문제

문제를 풀다가 트리를 다시 알아둬야할 것 같아서 복습겸 

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

이진 트리

이진 트리에 대한 개념은 많은 곳에서 더 자세히 설명하고 있기 때문에 생략

자바스크립트로 이진 트리를 구현하기 위해선 노드가 필요하다

여기서 노드는 value, 그리고 자기가 가르키고 있는 왼쪽, 오른쪽 대한 정보를 가지고 있다

이진 트리는 노드로 구성되어있는 자료구조다

위 문제를 풀기 위한 트리의 구현은 다음과 같다

트리 구현

class Node{
        constructor(x, y, value) {
            this.value = value;
            this.x = x;
            this.y = y;
            this.left = null;
            this.right = null;
        }
    }
    class BinaryTree{
        constructor(node) {
            this.root = node;
        }
        insert(arr){
            if(!this.root) {
                this.root = new Node(...arr);
                return ;
            }
            if(arr[0]<this.root.x){
                if(!this.root.left){
                    this.root.left = new BinaryTree(new Node(...arr));
                    return ;
                }
                this.root.left.insert(arr);
                return ;
            }
            if(!this.root.right) {
                this.root.right= new BinaryTree(new Node(...arr));
                return ;
            }
            this.root.right.insert(arr);
        }
    }

순회만을 필요로하는 트리이기 때문에 다른 기능은 넣지 않고 트리만 구현했다

주어진 정보로 트리를 만들어야하는데 index를 벨류로, y의 크기로 level이, x의 값으로 트리의 좌,우가 결정된다

이를 바탕으로 정렬하면 쉽게 트리를 생성할 수 있다

정렬

    const arr = nodeinfo.map((v,i)=>v.concat(i+1)).sort((a, b) => {
      return b[1] !== a[1] ? b[1]-a[1] : a[0]-b[0];
    });

순회

    function preorder(node) {
        const stack = [node];
        const path = [];
        while (stack.length){
            const temp = stack.pop();
            path.push(temp.root.value);
            if(temp.root.right) stack.push(temp.root.right);
            if(temp.root.left) stack.push(temp.root.left);
        }
        return path;
    }

    function postOrder(node) {
        const stack = [node];
        const path = [];

        while (stack.length){
            const temp = stack.pop();
            path.push(temp.root.value);
            if(temp.root.left) stack.push(temp.root.left);
            if(temp.root.right) stack.push(temp.root.right);
        }
        path.reverse();
        return path;
    }

전위 순회와 후위 순회

재귀가 아닌 스택을 이용해서 구현했다

전체 코드

    class Node{
        constructor(x, y, value) {
            this.value = value;
            this.x = x;
            this.y = y;
            this.left = null;
            this.right = null;
        }
    }
    class BinaryTree{
        constructor(node) {
            this.root = node;
        }
        insert(arr){
            if(!this.root) {
                this.root = new Node(...arr);
                return ;
            }
            if(arr[0]<this.root.x){
                if(!this.root.left){
                    this.root.left = new BinaryTree(new Node(...arr));
                    return ;
                }
                this.root.left.insert(arr);
                return ;
            }
            if(!this.root.right) {
                this.root.right= new BinaryTree(new Node(...arr));
                return ;
            }
            this.root.right.insert(arr);
        }
    }
    function makeTree(arr){
        const bt = new BinaryTree();
        while (arr.length){
            const temp = arr.shift();
            bt.insert(temp);
        }
        return bt;
    }




    function preorder(node) {
        const stack = [node];
        const path = [];
        while (stack.length){
            const temp = stack.pop();
            path.push(temp.root.value);
            if(temp.root.right) stack.push(temp.root.right);
            if(temp.root.left) stack.push(temp.root.left);
        }
        return path;
    }

    function postOrder(node) {
        const stack = [node];
        const path = [];

        while (stack.length){
            const temp = stack.pop();
            path.push(temp.root.value);
            if(temp.root.left) stack.push(temp.root.left);
            if(temp.root.right) stack.push(temp.root.right);
        }
        path.reverse();
        return path;
    }

    solution([[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]);


    function solution(nodeinfo) {
        var answer = [];
        const arr = nodeinfo.map((v,i)=>v.concat(i+1)).sort((a, b) => {
            return b[1] !== a[1] ? b[1]-a[1] : a[0]-b[0];
        });

        const tree = makeTree(arr);

        answer.push(preorder(tree));
        answer.push(postOrder(tree));
        return answer;
    }