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

[문제 설명]

programmers.co.kr/learn/courses/30/lessons/42892

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

 

[풀이 과정]

이진 탐색 트리(Binary Search Tree)의 개념을 확실히 알 고 있는지 보는 문제다. 

1. 이진 탐색 트리를 만들 수 있는지.

2. 전위 순회(preOrder)로 이진 탐색트리를 조회 할 수 있는지.

3. 후위 순회(postOrder)로 이진 탐색트리를 조회 할 수 있는지. 

 

풀이 과정은 다음과 같다. 

1) 노드 클래스 만들기

이진 탐색 트리를 구현할 때 가장 먼저 준비되어야 하는 것은 트리의 노드다. 

노드는 아래의 3개 필드를 가진다. 

① Data: 노드의 실질적 데이터가 들어가는 필드

② Left: 노드의 왼쪽 서브트리 

③ Right: 노드의 오른쪽 서브트리 

 

그림으로 그리면 쉽게 이해할 수 있다. 

그럼 data 필드에 들어갈 것은?

트리 구성과, 정답에 필요한 값은 총 3가지다. 각 노드의 x좌표, y좌표, 그리고 배열에 몇번째로 들어있는지 index 값. 

data 필드에 들어가야할 데이터가 총 3개이므로 별도의 Data 클래스를 만들었다. (전체 코드는 가장 아래 있다.)

public static class Data {
        int num; // nodeinfo 배열에서 몇번째인지 index 값 
        int x;
        int y;

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

 

Data 클래스를 만들었으므로 Node 클래스까지 만든다. 

public static class Node {
        private Data data; // 실질적인 데이터가 들어가는 필드
        private Node left; // 노드의 왼쪽 서브 트리 
        private Node right; // 노드의 오른쪽 서브 트리 

        /**
         * 생성자 
         * @param data
         */
        public Node(Data data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

 

2)  트리 생성

이제 문제에서 제공하는 int[][]nodeinfo 배열과, 위에서 만든 Data, Node 클래스로 트리를 만든다. 

 

이진 탐색 트리의 삽입 연산 메소드를 통해 트리를 만들건데, 트리가 null일때 가장 처음으로 삽입되는 노드가 트리의 root 노드가 된다.

때문에 처음 삽입되는 노드가 트리 생성에 아주 중요하다. 

 

 

문제에서 제공하는 예시의 배열과, 배열 중 root 노드가 되는 좌표는 아래와 같다. 

또한 문제에서는 다음과 같은 규칙을 준다. 

• 규칙 : 자식 노드의 y 값은 항상 부모 노드보다 작다. 
• int nodeinfo[][] : {{5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2}};
• root node:  {8, 6}

즉, 삽입 연산 메소드로 트리 생성을 할 때, y 값이 가장 큰 좌표값부터 삽입해야 한다.

그렇다면, 애초에 배열이 y 값을 기준으로 정렬이 되어 있으면 좋겠다. 

 

그런데, answer에 출력되어야 할 값은 각 좌표값의 본래 index 값들이다.

무슨 말이냐면, int[][] nodeinfo에서 {8,6}은 배열의 7번째 순서에 있다. 이 값이 answer을 출력할 때 필요하다. 

그런데 y값으로 정렬을 해버리면 {8,6}은 배열에서 첫번째 순서가 되어버리기 때문에 원래 순서값을 미리! 저장을 해놓아야 한다. 

때문에, 배열을 순회하여 Data 클래스를 만들어 List<Data> dataList를 하나 만들었다. 

List<Data> dataList = new ArrayList<>();

for (int i = 0; i < nodeinfo.length; i++) {
   Data data = new Data(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
   dataList.add(data);
}

 

그런 다음에, dataList를 y 값을 기준으로 정렬한다. 

Arrays.sort(nodeinfo, (o1, o2) -> {
       int result = Integer.compare(o1[1], o2[1]);
       if (result == 0) {
           return Integer.compare(o1[0], o2[0]);
       }else {
           return  -result;
       }
});

 

이제 for문으로 dataList를 순회하며 각 Node를 만들고 트리에 삽입하면 된다. 

삽입 연산 메소드는 다음과 같다. 

    public static void insertNode(Data data) {
        Node newNode = new Node(data);

        if (root == null) {
            root = newNode;
            return;
        }

        Node currentNode = root;
        Node parentNode;
        while (true) {
            parentNode = currentNode;

            if (data.x < currentNode.data.x) {
                currentNode = currentNode.left;
                if (currentNode == null) {
                    parentNode.left = newNode;
                    return;
                }
            } else {
                currentNode = currentNode.right;
                if (currentNode == null) {
                    parentNode.right = newNode;
                    return;
                }
            }
        }
    }

 

3) 전위 순회(pre order)

전위 순회는 V(root) -> L(left) -> R(Right) 순서로 트리를 탐색한다. 

public static void preOrder(Node root) {
        if (root != null) {
            preOrderList.add(root.data.num);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

 

4) 후위 순회(post order)

후위 순회는 L(left) -> R(Right) -> V(root) 순서로 트리를 탐색한다.

    public static void postOrder(Node root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            postOrderList.add(root.data.num);
        }
    }

 

느낀점:

코드는 길지만 이진 탐색트리 및 트리 순회에 대한 개념과 코드를 확실히 안다면 충분히 풀 수 있는 문제다. 

창의력을 요하는 문제라기 보다는 탄탄한 개념이 중요한 문제!

하지만 트리에 대한 코드를 평소에 줄줄 욀 수는 없으니 코테 전날 빡세게 외워야 할 듯.

[Java code]

전체 코드

package kakao.blind2019;

import java.util.*;

/**
 * 길 찾기 게임
 * 소요 시간:
 */
public class Test01 {

    public static void main(String[] args) {
        int[][] nodeinfo = {{5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2}};
        int[][] answer = solution(nodeinfo);

        for (int i = 0; i < answer.length; i++) {
            System.out.println(Arrays.toString(answer[i]));
        }
    }

    public static class Data {
        int num;
        int x;
        int y;

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

    public static class Node {
        private Data data;
        private Node left;
        private Node right;

        public Node(Data data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public static Node root = null;
    public static List<Integer> preOrderList = new ArrayList<>(); // 전위순회 리스트
    public static List<Integer> postOrderList = new ArrayList<>(); // 후외순회 리스트

    public static int[][] solution(int[][] nodeinfo) {
        List<Data> dataList = new ArrayList<>();
        for (int i = 0; i < nodeinfo.length; i++) {
            Data data = new Data(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
            dataList.add(data);
        }

        Arrays.sort(nodeinfo, (o1, o2) -> {
            int result = Integer.compare(o1[1], o2[1]);
            if (result == 0) {
                return Integer.compare(o1[0], o2[0]);
            }else {
                return  -result;
            }
        });

        Collections.sort(dataList, (o1, o2) -> {
            if (o1.y == o2.y) {
                return o1.x - o2.x;
            }
            return o2.y - o1.y;
        });

        for (Data data : dataList) {
            insertNode(data);
        }

        // 전위 순회
        preOrder(root);
        // 후위 순회
        postOrder(root);

        int[][] answer = new int[2][preOrderList.size()];
        for (int i = 0; i < preOrderList.size(); i++) {
            answer[0][i] = preOrderList.get(i);
            answer[1][i] = postOrderList.get(i);
        }

        return answer;
    }

    // 트리에 노드 삽입
    public static void insertNode(Data data) {
        Node newNode = new Node(data); // 노드 생성

        if (root == null) {
            root = newNode;
            return;
        }

        Node currentNode = root;
        Node parentNode;

        while (true) {
            parentNode = currentNode;

            if (data.x < currentNode.data.x) {
                currentNode = currentNode.left;

                if (currentNode == null) {
                    parentNode.left = newNode;
                    return;
                }
            } else {
                currentNode = currentNode.right;
                if (currentNode == null) {
                    parentNode.right = newNode;
                    return;
                }
            }
        }
    }

    // 전위 순회 (V -> L -> R)
    public static void preOrder(Node root) {
        if (root != null) {
            preOrderList.add(root.data.num);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 후위 순회(L -> R -> V)
    public static void postOrder(Node root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            postOrderList.add(root.data.num);
        }
    }
}