[프로그래머스(Programmers)] 길 찾기 게임 (java, 그래프/전위순회/후위순회)

안녕하세요. 오늘은 프로그래머스의 길 찾기 게임 문제를 풀어보도록 하겠습니다.

문제 링크

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

전체 코드

import java.util.*;

class Solution {
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int [2][nodeinfo.length];
        LinkedList<Node> tree = new LinkedList<>();

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

        // 노드를 y가 높은 순으로 정렬(내림차순), y가 같으면 x가 낮은 순으로(오름차순) 정렬
        // parent를 구하는 과정(상위 노드부터 하위 노드까지 정렬하는 과정)
        Collections.sort(tree, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.y > o2.y)             return -1;
                else if (o1.y < o2.y)       return 1;
                else {
                    if(o1.x > o2.x)         return 1;
                    else if (o1.x < o2.x)   return -1;
                    else                    return 0;
                }
            }
        });

        Node root = tree.get(0);

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

        preorder(answer, root);
        idx = 0;
        postorder(answer, root);

        return answer;
    }

    static int idx = 0;
    
    
    void addNode(Node parent, Node child){
        if(parent.x > child.x) {
            if(parent.left == null){
                parent.left = child;
            } else {
                addNode(parent.left, child);
            }
        } else {
            if(parent.right == null) {
                parent.right = child;
            } else {
                addNode(parent.right, child);
            }
        }
    }

    void preorder(int[][] arr, Node root) {
        if(root != null) {
            arr[0][idx++] = root.num;
            preorder(arr, root.left);
            preorder(arr, root.right);
        }
    }

    void postorder(int[][] arr, Node root){
        if(root != null) {
            postorder(arr, root.left);
            postorder(arr, root.right);
            arr[1][idx++] = root.num;
        }
    }
}

class Node {
    int x;
    int y;
    int num;
    Node left;
    Node right;

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

[참고한 곳]
https://kosaf04pyh.tistory.com/143