프로그래머스 - 길 찾기 게임(Java)

트리 문제입니다.

 

양의 정수로 이루어진 (x, y)좌표가 주어졌을 때, 이진 탐색 트리로 만들어 전위 및 후위 탐색을 하면 되는 문제입니다.

문제 조건에 주어졌다싶이, 이진 탐색 트리는 세 가지 조건을 만족해야 합니다.

1. 부모의 키는 유일해야 한다. 
2. 왼쪽 자식 노드의 키는 부모의 키 보다 작다.
3. 오른쪽 자식 노드의 키는 부모의 키 보다 작다.

문제 조건에 의해 각 노드의 x값은 고유하므로 1번 조건이 성립합니다.

 

트리를 만드는 방법은 간단합니다.

우선 주어진 입력을 y의 값 기준으로 정렬하되, 같은 y값이라면 x가 작은 순으로 정렬해야 합니다.

높은 레벨(level)을 가진 노드부터 앞 쪽으로 정렬이 되기 때문에, 그 순서대로 트리를 만들기 시작하면 됩니다.

이 때, 노드의 x값을 기준으로 자식 노드를 추가하면 됩니다.

private static void makeTree(Node parent, Node child) {
    if (parent.x > child.x) {
        if (parent.left == null) {
            parent.left = child;
        } else {
            makeTree(parent.left, child);
        }
    } else {
        if (parent.right == null) {
            parent.right = child;
        } else {
            makeTree(parent.right, child);
        }
    }
}

 

탐색은 왼쪽 자식 노드부터 탐색을 하면 됩니다.

단, 탐색할 때 어디에다가 노드의 값을 출력할지에 따라 탐색 결과가 달라집니다.

우선 코드먼저 보고 오시죠.

// 전위
private static void preSearch(Node node) {
    if (node != null) {
        System.out.println(node.value);
        preSearch(node.left);
        preSearch(node.right);
    }
}

// 후위
private static void postSearch(Node node) {
    if (node != null) {
        postSearch(node.left);
        postSearch(node.right);
        System.out.println(node.value);
    }
}

 

두 메소드의 차이점이 보이시나요?

전위의 경우 맨 앞에, 후위의 경우 맨 뒤에 출력문이 있습니다.

둘 다 똑같이 왼쪽 자식 노드먼저 탐색을 하지만, 출력문 위치에 따라 탐색 결과가 달라집니다.

추가로 중위 탐색은 어떻게 될까요?

당연히 중간에 출력문이 있겠네요.

 

[구현 코드]

import java.util.*;

class Solution {
    private static Node[] nodes;
    private static List<Integer> preList, postList;

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

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

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

        Arrays.sort(nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.y == o2.y) return o1.x - o2.x; // y축이 같으면 x가 작은 쪽으로 정렬
                return o2.y - o1.y; // y축이 큰 쪽으로 정렬
            }
        });

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

        preList = new ArrayList<>();
        preSearch(root);

        postList = new ArrayList<>();
        postSearch(root);

        int[][] answer = new int[2][nodeinfo.length];

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

        return answer;
    }

    private static void preSearch(Node node) {
        if (node != null) {
            preList.add(node.value);
            preSearch(node.left);
            preSearch(node.right);
        }
    }

    private static void postSearch(Node node) {
        if (node != null) {
            postSearch(node.left);
            postSearch(node.right);
            postList.add(node.value);
        }
    }

    private static void makeTree(Node parent, Node child) {
        // 부모가 크면 왼쪽 자식 노드
        if (parent.x > child.x) {
            if (parent.left == null) {
                parent.left = child;
            } else {
                makeTree(parent.left, child);
            }
        } else {
            if (parent.right == null) {
                parent.right = child;
            } else {
                makeTree(parent.right, child);
            }
        }
    }
}