이번에 풀어본 문제는
프로그래머스 길 찾기 게임 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Node
{
    int x, y, val;
    Node left,right;

    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
class Solution {
    static List<Node> tree;
    static int orderIdx;
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer;

        int nodeInfo_row = nodeinfo.length;
        tree = new ArrayList<>();

        for (int i = 0; i < nodeInfo_row; i++) {
            int x = nodeinfo[i][0];
            int y = nodeinfo[i][1];

            tree.add(new Node(x, y, i + 1));
        }
        tree.sort((o1, o2) -> o2.y - o1.y); // y를 기준으로 내림차순

        Node root = tree.get(0);

        int tree_size = tree.size();
        for (int i = 1; i < tree_size; i++) {
            link(root, tree.get(i));
        }

        answer = new int[2][nodeInfo_row];
        //전위
        preOrder(root, answer[0]);
        orderIdx = 0;
        //후위
        postOrder(root, answer[1]);
        return answer;
    }
    static void link(Node parent, Node child) {
        // 왼쪽
        if (parent.x > child.x) {
            //왼쪽이 비어있으면
            if (parent.left == null) {
                parent.left = child;
            }
            // 이미 채워져있으면
            else {
                link(parent.left, child);
            }
        }
        // 오른쪽
        else {
            if (parent.right == null) {
                parent.right = child;
            }
            else {
                link(parent.right, child);
            }
        }
    }

    static void preOrder(Node node, int [] arr) {
        if (node != null) {
            arr[orderIdx++] = node.val;
            preOrder(node.left, arr);
            preOrder(node.right, arr);
        }
    }

    static void postOrder(Node node, int [] arr) {
        if (node != null) {
            postOrder(node.left, arr);
            postOrder(node.right, arr);
            arr[orderIdx++] = node.val;
        }
    }
}

📝 풀이

주어진 입력값으로 트리를 완성하여 전위, 후위 순회의 결괏값을 반환하는 문제입니다. y값이 클 수록 높은 레벨이므로, 노드를 y값을 기준으로 정렬한 후 트리를 연결해주면 됩니다.
x값이 작으면 왼쪽자식, 크면 오른쪽 자식입니다.
트리를 완성했다면 전위, 후위 순회의 결괏값을 배열에 담아 리턴해주면 해결할 수 있습니다.

📜 후기

재귀를 사용한 트리구조 연결만 구현하면 어렵지 않았던 문제 같습니다.