길 찾기 게임 [자바]

 

🧫 문제 분석

✔️ 출처

길 찾기 게임 level 3

📖 문제

생각보다 재밌는 문제였다.

 

입력으로 노드의 좌표값만 주어지고

 

 

해당 조건에 맞게 이진트리를 만들어야하는데 

최상위 루트 부터 시작해서 자식노드를 추가하는 식으로 생각했다.

 

따라서 y값을 기준으로 내림차순 정렬하고, 같다면 x값을 기준으로 오름차순 정렬한다.

 

좀 복잡한데 코드를 보면 그나마 이해가 된다.

 

자식을 추가할때 주의할 점은

다른 노드가 자식으로 가져야할 노드를 자식노드로 설정하게 될 때도 있다.

이를 방지하기 위해서는 추가가능한 범위를 지정해줘야한다.

 

즉, 각 서브트리의 범위 x의 범위를 지정해서 해당 범위 안에 든 노드라면 자식으로 추가하는 것이다.

범위는 트리 구성 조건 5,6번을 참고하면 된다. 

 

 

예시)

 위와 같은 케이스가 발생할 수 있다. 

 

따라서 각 서브 트리의 루트 x값을 기준으로 범위를 나눠

해당 범위 안에 들면서 트리생성조건에 맞다면 자식노드로 추가한다.

---

🔅 문제 풀이

import java.util.*;


class Solution {
    
    class Node {
        int n, x, y;
        Node left;
        Node right;
        
        public Node (int n, int x, int y) {
            this.n = n;
            this.x = x;
            this.y = y;
            left = null;
            right = null;
        }
    }
    
    static List<Node> list = new ArrayList<>();
    static boolean[] visited;
    static int[][] answer;
    
    static int preOrderIdx = 0;
    static int postOrderIdx = 0;
    
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        
        // 노드 객체로 생성후 리스트에 담기
        for (int i = 0; i < nodeinfo.length; i++) {
            int x = nodeinfo[i][0];
            int y = nodeinfo[i][1];
            list.add(new Node(i+1,x,y));
        }
        
        visited = new boolean[nodeinfo.length + 1];
        Collections.sort(list, (a, b) -> b.y == a.y ? a.x - b.x : b.y - a.y); // y가 큰순으로, 같다면 x가 작은 순으로 
        
        Node head = list.get(0); // 이진 트리이므로 항상 루트가 있을 것이다. 
        visited[head.n] = true;
        
        buildBinaryTree(head, 1, 0, 100000); // 이진트리의 자식 노드를 설정할 수 있는 범위를 정해 올바른 이진트리생성
        
        // 전위, 후위 노드 탐색 
        preOrder(head);
        postOrder(head);
        
        return answer;
    }
    
    private void preOrder(Node cur) {
        if (cur == null) {
            return;
        }
        answer[0][preOrderIdx++] = cur.n;
        preOrder(cur.left);
        preOrder(cur.right);
    }
    
    
    private void postOrder(Node cur) {
        if (cur == null) {
            return;
        }
        postOrder(cur.left);
        postOrder(cur.right);
        answer[1][postOrderIdx++] = cur.n;
    }
    
    private void buildBinaryTree(Node cur, int idx, int l, int r) {
        
        for (int i = idx; i < list.size(); i++) {
            Node tmp = list.get(i);
            if (visited[tmp.n] // 이미 사용한 노드
                || cur.y == tmp.y) continue;    // 같은 level의 노드 
            
            // 자식노드 추가 가능한 범위를 벗어남
            if(tmp.x < l || tmp.x > r) break;
            
            if (cur.left == null && tmp.x < cur.x) {
                cur.left = tmp;
                visited[tmp.n] = true;
                buildBinaryTree(tmp, i + 1, l, cur.x);
                
            } else if (cur.right == null && tmp.x > cur.x) {
                cur.right = tmp;
                visited[tmp.n] = true;
                buildBinaryTree(tmp, i + 1, cur.x, r);
            }
            
            if (cur.left != null && cur.right != null) {
                break;
            }
            
        }
        
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식