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

길 찾기 게임 : https://programmers.co.kr/learn/courses/30/lessons/42892

---

Problem

---

Solution

트리노드를 구성하는데 쓸데 없는 예외처리와 가능성을 생각하다보니 주어진 조건을 생각못하고 너무 어렵게 생각했다.

재귀함수를 통해 Node들을 연결시켜주고 DFS를 통해 전위 순회와 후위 순회를 수행시켜주면 된다.

문제 풀이는 아래와 같다.

1. Node 클래스를 만들어 각 노드를 저장한다(nodes).
2. y축을 기준으로 내림차순, y축이 같다면 x축 기준으로 오름차순으로 정렬한다.
3. nodes[0]가 가장 큰 y축을 가지므로 root가 된다.
4. root를 기준으로 nodes에 저장된 노드들을 차례로 비교하며 트리를 만들어준다.
5. 만들어진 트리를 전위 순회dfs와 후위 순회 dfs를 통해 각각의 리스트를 반환해준다.

---

Code

import java.util.*;
class Solution {
    public int[][] solution(int[][] nodeinfo) {
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0;i<nodeinfo.length;i++){
            nodes[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1], null,null);
        }
        //y좌표를 내림차순, 같은 깊이라면 x좌표 오름차순
        Arrays.sort(nodes, new Comparator<Node>(){
            @Override
            public int compare(Node o1, Node o2){
                if(o1.y==o2.y){
                    return o1.x-o1.x;
                }else{
                    return o2.y-o1.y;
                }  
            }
        });
        
        //저장된 nodes의 첫번째 Node가 root
        Node root = nodes[0];
        for(int i=0;i<nodes.length;i++){
            setLink(root, nodes[i]);
        }
        
        List<Integer> prevList = new ArrayList<>();
        List<Integer> postList = new ArrayList<>();
        int[] postArr = new int[nodes.length];
        setPrev(root, prevList);
        setPost(root, postList);
        
        int[][] answer = new int[2][nodes.length];
        for(int i=0;i<nodes.length;i++){
            answer[0][i] = prevList.get(i);
            answer[1][i] = postList.get(i);
        }
        return answer;
    }
    
    //전위순회
    //부모노드 -> 왼쪽자식노드 -> 오른쪽자식노드
    void setPrev(Node node, List<Integer> prevList){
        if(node == null) return;
        
        prevList.add(node.num);
        setPrev(node.left, prevList);
        setPrev(node.right, prevList);
    }
    
    //후위순회
    //왼쪽자식노드 -> 오른쪽자식노드 -> 부모노드
    void setPost(Node node, List<Integer> postList){
        if(node == null) return;
        
        setPost(node.left, postList);
        setPost(node.right, postList);
        postList.add(node.num);
    }
    
    //이진 트리 생성
    void setLink(Node parents, Node child){
    	//두 node가 같은 레벨이면 자식 노드로 만들수 없다.
        if(parents.y == child.y) return;
        //왼쪽 자식노드는 항상 부모노드의 x값보다 작다
        if(parents.x>child.x){
        	//부모노드의 왼쪽 자식노드가 없다면 child가 왼쪽 자식노드로 들어간다.
            if(parents.left==null){
                parents.left = child;
            }
            //부모노드의 왼쪽 자식노드가 있다면 왼쪽 자식노드를 부모노드로 생각하고 재귀
            else{
                setLink(parents.left, child);
            }
        }
        //오른쪽 자식노드는 부모 노드의 x값보다 크다.
        else{
        	//오른쪽 자식노드가 없다면 child는 부모의 오른쪽 자식노드로 들어간다.
            if(parents.right==null){
                parents.right = child;
            }
            //오른쪽 자식노드가 있다면 오른쪽 자식노드를 부모노드로 생각하고 재귀
            else{
                setLink(parents.right, child);
            }
        }
    }
    
    class Node{
        int num;
        int x;
        int y;
        Node left;
        Node right;
        public Node(int num, int x, int y, Node left, Node right){
            this.num = num;
            this.x = x;
            this.y = y;
            this.left = left;
            this.right = right;
        }
    }
}

---

Result

---

Reference