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

이 문제는 이진 트리의 탐색을 이용한 문제이다.

 

2차원 좌표로 점들이 주어지고, 이들을 이진 트리로 간주하여 전위, 후위 순회 결과를 찾는 문제이다.

 

중요한 점은 x좌표가 같은 것이 하나도 없다는 사실이다. 또한 이진 트리를 중위 순회하면 오름차순으로 정렬된다는 사실도 굉장히 중요하다.

이를 이용하면 x좌표로 오름차순 정렬한 노드들의 순서가 곧 중위 순회한 결과를 나타내게 된다.

 

그러면 문제가 중위 순회 결과가 주어졌을 때, 전위 및 후위 순회의 결과를 나타내는 문제로 바뀌게 된다.

 

일정 구간 안에서 가장 y좌표가 높은 노드가 루트임을 이용하여 문제를 쉽게 풀 수 있었다.

import java.util.*;
import java.io.*;

class Solution {
    
    Node[] inorder;
    List<Integer> preorder = new ArrayList<>();
    List<Integer> postorder = new ArrayList<>();
    
    public int[][] solution(int[][] nodeinfo) {
        init(nodeinfo);
        
        // test
        // printInorder();
        
        pre(0, inorder.length - 1);
        post(0, inorder.length - 1);
        
        int[][] answer = new int[2][];
        
        answer[0] = preorder.stream().mapToInt(Integer::intValue).toArray();
        answer[1] = postorder.stream().mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
    
    void pre(final int start, final int end) {
        if (start > end) {
            return;
        }
        
        final int rootIndex = findRootIndex(start, end);
        
        final int root = inorder[rootIndex].num;
        
        preorder.add(root);
        pre(start, rootIndex - 1);
        pre(rootIndex + 1, end);
    }
    
    void post(final int start, final int end) {
        if (start > end) {
            return;
        }
        
        final int rootIndex = findRootIndex(start, end);
        
        final int root = inorder[rootIndex].num;
        
        post(start, rootIndex - 1);
        post(rootIndex + 1, end);
        postorder.add(root);
    }
    
    int findRootIndex(final int start, final int end) {
        
        int highY = -1;
        int result = -1;
        
        for (int i = start; i <= end; i++) {
            final int num = inorder[i].num;
            final int y = inorder[i].y;
            final int x = inorder[i].x;
            
            if (highY < y) {
                highY = y;
                result = i;
            }
        }
        
        return result;
    }

    void init(final int[][] nodeinfo) {
        List<Node> temp = new ArrayList<>();
        
        for (int i = 0; i < nodeinfo.length; i++) {
            final int num = i + 1;
            final int y = nodeinfo[i][1];
            final int x = nodeinfo[i][0];
            
            temp.add(new Node(num, y, x));
        }
        
        Collections.sort(temp, (e1, e2) -> {
            if (e1.x < e2.x) {
                return -1;
            }
            return 1;
        });
    
        inorder = new Node[temp.size()];
        
        for (int i = 0; i < temp.size(); i++) {
            inorder[i] = temp.get(i);
        }
    }
    
    static class Node {
        int num;
        int y;
        int x;
        
        Node(int num, int y, int x) {
            this.num = num;
            this.y = y;
            this.x = x;
        }
    }   
}