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

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

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

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

풀이

입력받은 데이터를 가지고 트리를 만들고, 전위순회/후위순회한 결과를 반환하면 된다. 트리에 대해 잘 알고 있었다면 크게 어려움 없이 풀 수 있는 문제였고 트리에 대해 잘 모르더라도 이 문제를 통해 트리를 이해하는데 도움이 될만한 좋은 문제라고 생각한다.

 

이 문제에서 요구되는 트리를 x값을 기준으로 생각한다면 이진검색트리라고 볼 수도 있을 것 같당.

 

트리들은 서로 연결되어 있어야 하므로 Node클래스를 만들어 x값, y값, value, 왼쪽 자식, 오른쪽 자식을 저장하도록 만들어 주었다.

 

입력받은 노드 정보를 문제의 조건에 맞는 트리 구조로 만들기 위해 정렬해 주었다. 이때 y값은 더 큰 값이 먼저 오도록, y값이 같다면 x값이 더 작은 값이 먼저 오도록 정렬해 주었다.

 

다음으로 정렬 후 0번 인덱스 값을 root로 지정하고 root를 기준으로 노드들을 insert해주었다. root보다 x값이 더 작다면 왼쪽으로, 더 크다면 오른쪽으로 insert해주었다. 이때 이미 왼쪽, 오른쪽 자식이 존재하면 자식의 값과 순환적으로 비교하여 적절한 위치를 찾아 주었다.

 

트리를 완성했다면 이제 순회만 해주면된다. 순회는 워낙 정형적인 알고리즘이라 어려울 것이 없었다. 

코드

import java.util.*;
 
class Solution {
    
    int[][] result;
    int idx;
    
    public int[][] solution(int[][] nodeinfo) {
        //노드를 입력받는다.
        Node[] node = new Node[nodeinfo.length];
        for(int i = 0; i < nodeinfo.length; i++) {
            node[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1, null, null);
        }
        //y값 큰 순서대로, y값 같다면 x값 작은 순서대로 정렬
        Arrays.sort(node, new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if(n1.y == n2.y) return n1.x - n2.x;
                else return n2.y - n1.y;
            }
        });
        
        //트리를 만든다.
        Node root = node[0];
        for(int i = 1; i < node.length; i++) {
            insertNode(root, node[i]); 
        }
        
        result = new int[2][nodeinfo.length];
        idx = 0;
        preorder(root); //전위 순회
        idx = 0;
        postorder(root); //후위 순회
        return result;
    }
    
    public 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);
        }
    }
    
    public void preorder(Node root) {
        if(root != null) {
            result[0][idx++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root) {
        if(root != null) {
            postorder(root.left);
            postorder(root.right);
            result[1][idx++] = root.value;
        }
    }
    
    public class Node {
        int x;
        int y;
        int value;
        Node left;
        Node right;
        
        public Node(int x, int y, int value, Node left, Node right) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}