[프로그래머스 | JAVA] 길 찾기 게임 (이진 트리, 순회)

keyword : 트리, 후위 순회, 전위 순회
https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

풀이

문제 설명은 장황하지만, 요구하는 바는 간단하게 축약된다.

1. 직접 이진 트리를 구현할 수 있는가?
2. 이진 트리의 순회 방법(전위 순회, 후위 순회)에 대해 아는가?

이 두 가지다.

맨 처음에는 배열을 이용해 이진 트리를 구현하려 했으나, 정렬한 배열의 인덱스를 맞추는 것이 쉽지 않았고, 때문에 클래스를 선언해서 노드를 저장하는 것이 더 간단하겠다고 판단했다.

1. 노드 번호, x, y 좌표, 자식 노드를 저장할 수 있는 Node 클래스를 선언했다.
2. Node 배열을 만든 후, 각 노드를 저장한다.
   • 이 시점에서 자식노드는 알 수 없으므로 null로 선언해야 한다.
3. Comparator를 이용해 y좌표 내림차순, x좌표 오름차순으로 노드 배열을 정렬한다.
   • 이렇게 정렬하면, root 노드부터 차례대로 노드를 배열할 수 있다.
4. 배열을 반복하며 트리를 만든다.
   • 부모의 x좌표보다 자식의 x좌표가 작다면 왼쪽 자식 노드
   • 부모의 x좌표보다 자식의 x좌표가 크다면 오른쪽 자식 노드
5. 전위 순회, 후위 순회를 진행한다.
   • 굳이 따로 탐색할 필요 없이, 하나의 메소드에서 두 순회를 진행해도 된다. 자세한 것은 코드를 보시길.

아마 이진 트리를 아는데, 노드를 어떻게 해야할지 모르겠다면 3번에서 막혔을 가능성이 높았을 것 같다. 나머지는 전형적인 이진 트리 구현, 순회 알고리즘이므로 그다지 어렵지 않을 것이다.

 

코드

import java.util.*;

class Solution {
    private List<Integer> preorderResult = new ArrayList<>();
    private List<Integer> postorderResult = new ArrayList<>();

    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(i+1, nodeinfo[i][0], nodeinfo[i][1]);
        }

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

        Node root = nodes[0];
        for(int i = 1; i < nodeinfo.length; i++) {
            insertNode(root, nodes[i]);
        }

        order(root);

        for(int i = 0; i < nodeinfo.length; i++) {
            answer[0][i] = preorderResult.get(i);
            answer[1][i] = postorderResult.get(i);
        }

        return answer;
    }

    private void insertNode(Node parent, Node child) {
        if(parent.x > child.x) { // 왼쪽 자식
            if(parent.left == null) {
                parent.left = child;
            } else {
                insertNode(parent.left, child);
            }            
        } else {
            if(parent.right == null) {
                parent.right = child;
            } else {
                insertNode(parent.right, child);
            }
        }
    }

    private void order(Node node) {
        if(node != null ){
            preorderResult.add(node.value);
            order(node.left);
            order(node.right);
            postorderResult.add(node.value);
        }
    }

    class Node {
        int value;
        int x, y;
        Node left;
        Node right;

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

 

여담

처음에는 별로 안 어렵겠다 싶었는데, 들어오는 입력을 트리로 바꾸는 것이 생각보다 어려웠다. 그래프 문제는 많이 풀어도 트리 문제는 많이 푼 적이 없어서 그런가? 그냥 이진 트리에 대한 개념이 부족했던 것 같기도 하다.

오랜만에 이진 트리 리마인드를 할 수 있는 문제였다. 2주 정도 뒤에 다시 한 번 풀어봐야겠다.