[프로그래머스] 길 찾기 게임 - JAVA

🔗 문제

프로그래머스

 

 

👨🏻‍💻 풀이 및 코드

전위 순회와 후위 순회는 전형적인 알고리즘이라 어려울 게 없지만, 주어진 노드들을 이용해 이진트리를 만드는 것이 까다로운 문제였습니다.

 

• 노드들의 연결을 위해 Node 클래스를 생성하여 해당 노드의 x좌표, y좌표, 노드의 번호, 왼쪽 노드, 오른쪽 노드 의 값을 저장합니다.  
• 주어진 노드들을 y좌표가 큰 순서대로 정렬합니다.  y좌표가 같다면 x좌표가 작은 순서대로 정렬합니다. 
• 정렬된 노드들 중 가장 첫 번째 노드가 root 노드가 되므로(가장 레벨이 높은 노드), 이 root 노드를 기준으로 차례대로 왼쪽 또는 오른쪽 노드에 노드들을 삽입합니다.
• 이때, 왼쪽 자식 노드의 조건은 root 노드의 x좌표보다 작아야 합니다. 
• 만약, 왼쪽 자식 노드가 이미 있다면, 해당 왼쪽 자식 노드가 root 노드가 되어 다시 재귀문을 돌아 비어있는 적절한 위치에 현재 노드를 삽입합니다.
• 오른쪽 자식 노드의 조건은 root 노드의 x좌표보다 크다는 조건을 빼고 동일합니다.

 

이렇게 만들어진 이진트리를 사용하여 전위 순회와 후위 순회 알고리즘을 사용하여 문제를 해결할 수 있습니다. 

 

전체 코드

import java.util.*;

class Solution {
    
    class Node {
        int x;
        int y;
        int num;
        Node left;
        Node right;
        
        Node(int x, int y, int num, Node left, Node right) {
            this.x = x;
            this.y = y;
            this.num = num;
            this.left = left;
            this.right = right;
        }
    }
    
    int idx;
    int[][] answer;
    
    public int[][] solution(int[][] nodeinfo) {
        Node[] 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++) {
            insertNode(root, nodes[i]);
        }
        
        answer = new int[2][nodes.length];
        idx = 0;
        preOrder(root);
        idx = 0;
        postOrder(root);
        return answer;
    }
    
    void insertNode(Node parent, Node node) {
        if(node.x < parent.x) {
            if(parent.left == null) parent.left = node;
            else insertNode(parent.left, node);
        } else {
            if(parent.right == null) parent.right = node;
            else insertNode(parent.right, node);
        }
    }
    
    void preOrder(Node node) {
        if(node != null) {
            answer[0][idx++] = node.num;
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    
    void postOrder(Node node) {
        if(node!=null) {
            postOrder(node.left);
            postOrder(node.right);
            answer[1][idx++] = node.num;
        }
        
    }
}