[프로그래머스] 길 찾기 게임 (java)

노드 클래스를 만드는게 포인트! 그리고 우선순위 큐를 이용해 x, y 좌표에 따라 정렬하는 것도 포인트!

 

import java.util.*;
class Solution {
    static int idx = 0;
    static class Node {
        int x;
        int y;
        int idx;
        Node left;
        Node right;
        
        Node(int x, int y, int idx){
            this.x = x;
            this.y = y;
            this.idx = idx;
            left = null;
            right = null;
        }
    }
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2) -> {
            return (n2.y > n1.y) ? 1 : (n1.y > n2.y) ? -1 : (n1.x >n2.x) ? 1 : (n2.x > n1.x) ? -1 : 0;
        });
        Node head = null, cur = null, prev = null;
        int[] pre = new int[nodeinfo.length];
        int[] post =new int[nodeinfo.length];
        answer[0] = pre;
        answer[1] = post;
        
        for(int i = 0; i < nodeinfo.length; i++)
            pq.offer(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
        
        head = pq.poll();
        while(!pq.isEmpty()){
            cur = head;
            Node node = pq.poll();
            while(cur != null){
                if(node.x < cur.x){
                    prev = cur;
                    cur = cur.left;
                } else if (node.x > cur.x) {
                    prev = cur;
                    cur = cur.right;
                }
            }
            if(prev.left == null && node.x < prev.x ) prev.left = node;
            if(prev.right == null && node.x > prev.x) prev.right = node;
        }
        
        preOrder(head, pre);
        idx = 0;
        postOrder(head, post);
        
        return answer;
    }
    
    static void preOrder(Node cur, int[] pre){
        if(cur == null) return;
        pre[idx++] = cur.idx;
        preOrder(cur.left, pre);
        preOrder(cur.right, pre);
    }
    static void postOrder(Node cur, int[] post){
        if(cur == null) return;
        postOrder(cur.left, post);
        postOrder(cur.right, post);
        post[idx++] = cur.idx;
    }
}

 

 

 

 

[참고]

https://artineer.tistory.com/118

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