2019 - 길 찾기 게임

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

코딩테스트 연습 - 길 찾기 게임

[ 문제풀이 ]

주어진 노드의 정보를 가지고 이진트리를 구성할 수 있다면 해결할 수 있는 문제이다.

​노드의 정보는 2차원 좌표에서의 x, y 값이며 모든 노드는 서로 다른 x 값을 가진다. 즉, 1. y가 큰 순, 2. x가 작은 순으로 정렬을 한 후 이진트리의 특징으로 노드들을 하나씩 연결해서 이진트리를 구성해 줄 수 있다.

​이진 트리에서의 전위 순회와 후위 순회 방법은 잘 알려져 있기 때문에 쉽게 해결할 수 있을 것이다.

import java.util.*;

class Solution {
    class Node implements Comparable<Node> {
        int idx, y, x;
        Node left, right;
        
        public Node (int idx, int x, int y) {
            this.idx = idx;
            this.x = x;
            this.y = y;
        }
        
        public int compareTo(Node o) {
            if (this.y == o.y) return this.x - o.x;
            return o.y - this.y;
        }
    }
    
    Node[] node;
    int[][] answer;
    int k;
    
    public int[][] solution(int[][] nodeinfo) {
        int n = nodeinfo.length;
        answer = new int[2][n];
        
        node = new Node[n];
        for (int i = 0; i < nodeinfo.length; ++i) {
            node[i] = new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
        }
        
        Arrays.sort(node);
        
        //root 노드를 기준으로 i번째 node를 연결
        for (int i = 1; i < n; ++i) {
            createBinaryTree(node[0], node[i]);
        }
        
        preOrder(node[0]);
        k = 0;
        postOrder(node[0]);
        
        return answer;
    }
    
    public void createBinaryTree(Node p, Node c) {
        //자식노드가 부모노드의 왼쪽인 경우
        if (p.x > c.x) {
            if (p.left == null) {
                p.left = c;
            } else {
                createBinaryTree(p.left, c);
            }
        } 
        //자식노드가 부모노드의 오른쪽인 경우
        else if (p.x < c.x) {
            if (p.right == null) {
                p.right = c;
            } else {
                createBinaryTree(p.right, c);
            }
        }
    }
    
    public void preOrder(Node root) {
        if (root == null) return;
        
        answer[0][k++] = root.idx;
        preOrder(root.left);
        preOrder(root.right);
    }
    
    public void postOrder(Node root) {
        if (root == null) return;
        
        postOrder(root.left);
        postOrder(root.right);
        answer[1][k++] = root.idx;
    }
}