2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임 <JAVA>

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

걸린시간  :  1 hour

문제 

 

전형적인 트리 구성문제 + 순회 문제

 

Node 클래스를 어떻게 설계하느냐에 따라 문제의 성패가 달린다고 생각했다.

 

노드의 좌표가 2차원 배열 [x,y] 로 존재 한다. 

ex - 1번 노드  [5,3] 

        2번 노드 [11,5] •••

 

일단 Root 노드를 탐색해야 좌 우 노드를 연결해서 전체적인 트리를 구성할 수 있다.

 

어떻게 하면 Root 노드를 구할까?? - > 노드 정보를 가진 2차원 배열을 y값 기준으로 내림차순 정렬 -> y값 같다면 x 값으로 오름차순 

 

트리를 구성하고 ???

 

순회하고???

 

answer 에다가 preorder , postorder 순으로 삽입 

 

끝!

 

 

 

class Node 

//노드를 만들어서 x,y 좌표 , 노드 번호 value , 좌 , 우 노드
class Node {
    public int x;
    public int y;
    public int value;
    public Node left; //왼쪽 자식 노드
    public Node right; //오른쪽 자식 노드
    
    public Node(int value,int x,int y,Node left,Node right) {
        this.x = x;
        this.y = y;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

 

Node 정보 초기화

Node[] node = new Node[nodeinfo.length];
        
for(int i=0; i<nodeinfo.length; i++) {
    node[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1],null,null);
}

 

노드정보를 정렬

//y값 기준으로 내림차순 정렬 -> y값 같다면 x 값 오름차순 정렬
Arrays.sort(node, new Comparator<Node>(){
    public int compare(Node a,Node b) {
        if(a.y == b.y) { //y값이 같다면
            return a.x - b.x; //x값 오름차순
        }
        return b.y - a.y; //y값 내림차순
    }
});

 

트리 생성

//트리생성
Node root = node[0]; //첫번째노드 -> root 노드가 된다
for(int i=1; i<node.length; i++) { //
    createTree(root,node[i]);
}



//이진 트리 생성
//임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
//임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
private static void createTree(Node parent, Node child) {
    if(parent.x > child.x) { // 왼쪽 서브트리
        if(parent.left == null) {
            parent.left = child;
        } else {
            createTree(parent.left, child);
        }
    } else { //오른쪽 서브트리
        if(parent.right == null) {
            parent.right = child;
        } else {
            createTree(parent.right, child);
        }
    }
}

 

전체 코드 

import java.util.*;
//노드를 만들어서 x,y 좌표 , 노드 번호 value , 좌 , 우 노드
class Node {
    public int x;
    public int y;
    public int value;
    public Node left; //왼쪽 자식 노드
    public Node right; //오른쪽 자식 노드
    
    public Node(int value,int x,int y,Node left,Node right) {
        this.x = x;
        this.y = y;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    static int[][] result;
    static int index;
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = {};
        Node[] node = new Node[nodeinfo.length];
        
        for(int i=0; i<nodeinfo.length; i++) {
            node[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1],null,null);
        }
        //y값 기준으로 내림차순 정렬 -> y값 같다면 x 값 오름차순 정렬
        Arrays.sort(node, 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 root = node[0];
        for(int i=1; i<node.length; i++) { //
            createTree(root,node[i]);
        }
        
        result = new int[2][nodeinfo.length];
        preorder(root);
        index = 0;
        postorder(root);
        
        return result;
    }
    //이진 트리 생성
    //임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
    //임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
    private static void createTree(Node parent, Node child) {
        if(parent.x > child.x) { // 왼쪽 서브트리
            if(parent.left == null) {
                parent.left = child;
            } else {
                createTree(parent.left, child);
            }
        } else {
            if(parent.right == null) {
                parent.right = child;
            } else {
                createTree(parent.right, child);
            }
        }
    }
    //preorder
    private static void preorder(Node root) {
        if(root != null) {
            result[0][index++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    //postorder
    private static void postorder(Node root) {
        if(root != null) {
            postorder(root.left);
            postorder(root.right);
            result[1][index++] = root.value;
        }
    }
}

 

 

총평

최근 트리관련 공부를 계속 했더니 트리를 보면 일단 겁먹지 않고 노드정보를 담는 클래스 생성을 먼저하게 되었다. 

그리고 전위 , 중위 , 후위 순회는 동작원리랑 어느정도 재귀의 감각이 있다면 눈감고도 풀 수 있어야 한다고 생각한다.

 

항상 헷갈리던게 Comparator 를 가지고 정렬하는 메서드를 만들어 내는 것이다.  맨날 외워야지 외워야지 하다가 결국 찾아서 풀어냈다.

이번 기회에 많은 정렬방법이 있는데 확실하게 딱 하나를 정해서 외우는게 중요하다고 느꼈다.