[JAVA] 길 찾기 게임

문제

https://programmers.co.kr/learn/courses/30/lessons/42892?language=java 

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

내 풀이

import java.util.*;
class Solution {
    
    class Node {
        public int idx;
        public int x;
        public int y;
        public Node left;
        public Node right;
        
        Node (int idx,int x, int y) {
            this.idx = idx;
            this.x = x;
            this.y = y;
        }
        
        public void setChild(Node child) {
            if (this.x < child.x) {
                if (this.right == null) this.right = child;
                else this.right.setChild(child);
            } else {
                if (this.left == null) this.left = child;
                else this.left.setChild(child);
            }
        }
    }
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        List<Node> nodes = new ArrayList<>();
        for(int i=0; i<nodeinfo.length; i++) {
            nodes.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        nodes.sort((a,b) -> {
            if(a.y== b.y) {
                return Integer.compare(a.x, b.x);
            } else {
                return Integer.compare(b.y, a.y);
            }
        });
        Node root = nodes.get(0);
        for(int i=1; i<nodes.size(); i++) {
            root.setChild(nodes.get(i));
        }
        
        List<Integer> pre = new ArrayList<>();
        preOrder(pre, root);
        answer[0] = pre.stream().mapToInt(i -> i).toArray();
        
        List<Integer> post = new ArrayList<>();
        postOrder(post, root);
        answer[1] = post.stream().mapToInt(i -> i).toArray();
        
        return answer;
    }
    
    public void preOrder(List<Integer> answer, Node node) {
        if (node == null) {
            return;
        }
        
        answer.add(node.idx);
        preOrder(answer, node.left);
        preOrder(answer, node.right);
    }
     
    public void postOrder(List<Integer> answer, Node node) {
        if (node == null) {
            return;
        }
        
        postOrder(answer, node.left);
        postOrder(answer, node.right);
        answer.add(node.idx);
    }
    
}

알게 된 것

• 항상 경로를 input으로 받아 DFS,BFS, 순회 하는 알고리즘을 풀었는데 내가 직접 자바로 트리 구조를 만드니 큰 공부가 되었다.
• Node 의 자식노드들을 재귀적으로 세팅하는 메서드를 앞으로 기억할 수 있을 듯 하다.

피드백

전위 순회(preOrder), 중위 순회(inOrder), 후위 순회(postOrder) 의 순서를 암기는 해두자. 옛날에도 종종 헷갈렸었다.

 

전위가 방문 후 왼쪽 오른쪽
중위가 왼쪽후 방문 후 오른쪽