Programmers, 길 찾기 게임 : Java

🔗 문제 링크

길 찾기 게임

 

🔎 문제 풀이

트리를 순회하면 된다. 이 문제는 좌표 값으로 주어지는 노드들을 트리로 구성해야한다는 점이 핵심이다.

이런 유형의 문제는 처음이라 ,, 트리에 대해 간단히 정리하면서 이해했다.

트리 (Tree)

트리를 순회하는 알고리즘은 코드만 처음 딱 보았을 때는 어렵다고 느꼈는데,

트리에 대해 이해하고 다시 보니 직관적이라서 오히려 이해하기가 쉬웠다.

 

그리고 이 문제에서 트리를 만드는 과정은 다음과 같다.

 

1) x 좌표, y 좌표, 노드 번호(=value), 왼쪽 자식,노드 오른쪽 자식 노드를 저장할 수 있도록 Node 클래스를 만든다.

2) 조건에 맞는 트리 구조로 만들기 위해 Comparator 인터페이스를 활용해 정렬한다. 

    • y 값은 더 큰 값이 먼저 오도록, y 값이 같다면 x 값이 더 작은 값이 먼저 오도록 한다.

3)  정렬 후 0번 인덱스 값을 root로 지정하고, root를 기준으로 노드를 insert 한다.

 

트리를 만들었으면 재귀를 활용해 전위 순회와 후위 순회를 해주면 된다.

 

특히, 트리를 만들기 위해 Node 클래스를 객체 배열로 선언하는 부분에서 객체 배열에 대해 새롭게 배웠다.

마찬가지로 Node 클래스를 변수로 선언하는 것도 새로웠다. 이런 경우는 참조변수로만 쓸 수가 있다고 한다.

 

Kakao Tech 블로그 문제 해설을 보니 이 문제 정답률이 7.4% 이다 ,, 

원리는 이해했지만, 막상 문제를 마주치면 당황할 것 같다.

트리 순회 알고리즘도 백준에서 몇 개 더 풀어봐야겠다 !

 

해당 문제 풀이는 객체 배열을 만드는 방법을 사용했지만 !

Kakao Tech에서는 Queue를 만들어 x축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 Queue에 넣어두고, Queue의 front를 확인하는 방법을 알려준다.

 

Key Point

🔑 좌표 값으로 주어지는 노드들을 트리로 구성한다.

🔑 트리 순회 알고리즘을 활용한다.

🔑 전위 순회는 노드 - 왼쪽 자식 - 오른쪽 자식 순이고, 후위 순회는 왼쪽 자식 - 오른쪽 자식 - 노드 순이다.

 

Java 코드

import java.util.*;

class Solution {
    
    int[][] answer;
    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]);
        }
        
        answer = new int[2][nodeinfo.length];
        idx = 0;
        preorder(root); // 전위 순회
        idx = 0;
        postorder(root); // 후위 순회
        
        return answer;
    }
    
    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) {
            answer[0][idx++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            answer[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;
        }
    }
}

 

 

---

Reference

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