[프로그래머스] 카카오_길찾기 게임 (자바 풀이)

문제

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

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

풀이

이 문제는 트리의 성질에 대해 잘 안다면 쉽게 해결할 수 있는 문제이다. 직접 이진트리를 구현하여 전위 순회, 후위 순회로 트리를 탐색하기만 하면 된다. 이때 이진트리를 구현하기 위해 Node 구조체를 만들어야 한다. 이후 y좌표가 큰 순서대로, y좌표가 같다면 x좌표가 작은 순서대로 정렬하여 저장한 리스트를 탐색하면서 이진트리를 구성하면 된다. 자세한 내용은 코드를 보면 이해가 빠르다. 

 

이진트리와 순회에 대해 알고싶다면 다음을 참고하자.

[자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현

코드

import java.util.*;
 
class Solution {
    static int[][] answer;
    static int idx;
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        ArrayList<Node> list = new ArrayList<>();
        for(int i=0; i<nodeinfo.length; i++){
            list.add( new Node(i+1, nodeinfo[i][0],nodeinfo[i][1],null,null));
        }
        Collections.sort(list);
        
        Node root = list.get(0);
        for(int i=1; i<list.size(); i++){
            insertNode(root, list.get(i));
        }
        
        idx = 0;
        preorder(root);
        idx = 0;
        postorder(root);  
        
        return answer;
    }
    
    // 전위 순회
    static void preorder(Node root) {
        if(root != null) {
            answer[0][idx++] = root.num;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    // 후위 순회    
    static void postorder(Node root) {
        if(root != null) {
            postorder(root.left);
            postorder(root.right);
            answer[1][idx++] = root.num;
        }
    }
    
    static void insertNode(Node parent, Node child){
        if(parent.x > child.x) {    // 왼쪽 자식노드
            if(parent.left == null) parent.left = child;
            else insertNode(parent.left, child);
        } else {    // 오른쪽 자식노드
            if(parent.right == null) parent.right = child;
            else insertNode(parent.right, child);
        }
    }
    
    static class Node implements Comparable<Node>{
        int num;
        int x;
        int y;
        Node left;  // 왼쪽 자식노드
        Node right; // 오른쪽 자식노드
        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;
        }
        
        // y좌표가 큰 순서대로, 같다면 x좌표가 작은 순서대로
        @Override
        public int compareTo(Node o1){
            if(this.y == o1.y){ 
                return this.x-o1.x; 
            }
            
            return o1.y-this.y;
        }
    }
}