[프로그래머스] 42892. 길 찾기 게임

문제 링크

[프로그래머스] 42892. 길 찾기 게임

풀이 과정

주어진 좌표들을 통해 이진 탐색 트리(Binary Search Tree, BST)를 구현하고, 전위 순회(preorder)와 후위 순회(postorder)의 결과를 리턴하는 문제입니다.

Collections.sort(list, new Comparator<Info>() {
    @Override
    public int compare(Info o1, Info o2) {
        return o1.y == o2.y ? o1.x - o2.x : o2.y - o1.y;
    }
});

문제에 주어진 규칙에 의해 동일한 BST의 형태를 맞추기 위하여, 주어진 nodeinfo 를 y좌표 내림차순으로(두 노드의 y좌표가 같다면 x좌표 오름차순으로) 정렬했습니다. 또한, 정점 번호를 정렬 후에도 기억하기 위해 Info 클래스를 만들어서 이 곳에 정점 번호와 좌표를 기록했습니다.

static class TreeNode {
    int index;
    int x;
    TreeNode left;
    TreeNode right;

    public TreeNode(int index, int x) {
        this.index = index;
        this.x = x;
    }
}

TreeNode 클래스는 각 노드가 가져야 되는 정보들을 멤버 변수로 선언해 두었습니다. 각 노드는 왼쪽 노드 및 오른쪽 노드 뿐 아니라, 문제에서 요구하는 정점의 번호와, 노드 삽입 시 비교 연산에 필요한 x 좌표도 갖습니다.

static class BinarySearchTree {
    TreeNode root;

    void insert(int index, int x) {
        TreeNode newNode = new TreeNode(index, x);

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

        TreeNode current = root;
        TreeNode parent = null;

        while (true) {
            parent = current;

            if (x < current.x) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    void preorder(TreeNode node) {
        if (node != null) answer[0][cnt++] = node.index;
        if (node.left != null) preorder(node.left);
        if (node.right != null) preorder(node.right);
    }

    void postorder(TreeNode node) {
        if (node.left != null) postorder(node.left);
        if (node.right != null) postorder(node.right);
        if (node != null) answer[1][cnt++] = node.index;
    }
}

BinarySearchTree 클래스는 TreeNode 객체들을 BST로 구조화하는 역할을 합니다. insert 메소드는 입력으로 들어온 노드의 x 좌표 값에 따라 왼쪽 자식으로 설정할 지, 오른쪽 자식으로 설정할 지 결정합니다. preorder 메소드는 현재 방문된 정점의 번호를 먼저 기록한 다음, 왼쪽 오른쪽 자식 순서로 재귀 함수를 호출해 배열을 채워갑니다. postorder 메소드는 먼저 왼쪽, 오른쪽 자식 순서로 재귀 함수를 호출하고, 반환되면 그제서야 정점의 번호를 기록합니다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
    static int[][] answer = {};
    static int cnt;

    public static int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];

        ArrayList<Info> list = new ArrayList<>();
        for (int i = 0; i < nodeinfo.length; i++) {
            list.add(new Info(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }

        Collections.sort(list, new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return o1.y == o2.y ? o1.x - o2.x : o2.y - o1.y;
            }
        });

        BinarySearchTree bst = new BinarySearchTree();
        for (Info info : list) {
            bst.insert(info.index, info.x);
        }

        bst.preorder(bst.root);

        cnt = 0;
        bst.postorder(bst.root);

        return answer;
    }

    static class Info {
        int index, x, y;

        public Info(int index, int x, int y) {
            this.index = index;
            this.x = x;
            this.y = y;
        }
    }

    static class TreeNode {
        int index;
        int x;
        TreeNode left;
        TreeNode right;

        public TreeNode(int index, int x) {
            this.index = index;
            this.x = x;
        }
    }

    static class BinarySearchTree {
        TreeNode root;

        void insert(int index, int x) {
            TreeNode newNode = new TreeNode(index, x);

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

            TreeNode current = root;
            TreeNode parent = null;

            while (true) {
                parent = current;

                if (x < current.x) {
                    current = current.left;
                    if (current == null) {
                        parent.left = newNode;
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        return;
                    }
                }
            }
        }

        void preorder(TreeNode node) {
            if (node != null) answer[0][cnt++] = node.index;
            if (node.left != null) preorder(node.left);
            if (node.right != null) preorder(node.right);
        }

        void postorder(TreeNode node) {
            if (node.left != null) postorder(node.left);
            if (node.right != null) postorder(node.right);
            if (node != null) answer[1][cnt++] = node.index;
        }
    }

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