(JAVA) 길 찾기 게임

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

풀이

이진트리를 사용한 기본적인 문제이다.

아래와 같은 순서로 구현해나가며 문제를 풀 수 있었다.

1. 트리에 사용할 Node 클래스 구현
2. nodes라는 node들을 담을 리스트에 node를 삽입
3. nodes를 y의 내림차순으로, y가 동일하다면 x의 오름차순으로 정렬 (트리에 올바른 순서대로 담기 위함)
4. 정렬된 리스트에서 node를 하나씩 꺼내면서 트리 만들기
5. 완성된 트리를 전위 순회한 값과 후위 순회한 값을 answer에 할당

import java.util.*;

class Solution {
    int[][] answer;
    int idx = 0;
    
    public int[][] solution(int[][] nodeinfo) {    
        answer = new int[2][nodeinfo.length];
        
        // nodes 배열에 node들 삽입
        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], null, null);
        }
        
        // node의 리스트를 올바른 순서로 정렬
        Arrays.sort(nodes, new Comparator<Node>(){
            @Override
            public int compare(Node n1, Node n2){
                if(n1.y == n2.y) return n1.x - n2.x;
                return n2.y - n1.y;
            }
        });
        
        // 정렬된 노드들로 트리를 만들기
        Node root = nodes[0];
            
        for (int i = 1; i < nodes.length; i++){
            makeTree(root, nodes[i]);
        }
        
        // 만들어진 트리들을 전위 순회, 후위 순회하며 answer에 할당
        preOrder(root);
        idx = 0;
        postOrder(root);
        
        return answer;
    }
    
    
    void makeTree(Node p, Node c){
        if(p.x > c.x){
            if(p.left == null) p.left = c;
            else makeTree(p.left, c);
        }
        else{
            if(p.right == null) p.right = c;
            else makeTree(p.right, c);
        }
    }

    void preOrder(Node root){
        if(root != null){
            answer[0][idx++] = root.id;
            preOrder(root.left);
            preOrder(root.right);        
        }
    }

    void postOrder(Node root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            answer[1][idx++] = root.id;
        }
    }
}

// 트리에 사용할 Node 클래스 구현
class Node {
    int id;
    int x;
    int y;

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