[programmers] 길 찾기 게임 (Java)

[길 찾기 게임]

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

프로그래머스

 

[접근 방법]

- 별도의 클래스로 Node 를 생성한다.

- 이진트리를 Root Node 를 기반으로 이진트리를 구축하는 메서드를 구연한다.

- 전위탐색 (중앙 노드 - 왼쪽 노드 - 오른쪽 노드) 하여, 리스트에 순서대로 추가한다.

- 후위탐색 (왼쪽 노드 - 오른쪽 노드 - 중앙 노드) 하여, 리스트에 순서대로 추가한다. 

[Java 코드]

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

import java.util.*;

class Solution {


    class Node {
        int x, y, idx;
        Node left, right;

        Node(int x, int y, int idx) {
            this.x = x;
            this.y = y;
            this.idx = idx;
        }
    }


    List<Integer> preorderList = new ArrayList<>();
    List<Integer> postorderList = new ArrayList<>();


    public int[][] solution(int[][] nodeinfo) {

        int n = nodeinfo.length; //node 개수
        Node[] nodes = new Node[n];

        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1);
        }

        /**node 정렬
         * 1. y 기준 내림차순
         * 2. x 기준 오름차순
         */
        Arrays.sort(nodes, (a, b) -> {
            if (a.y == b.y) {
                return a.x - b.x;
            }
            return b.y - a.y;
        });

        //root node 지정
        Node root = nodes[0];

        //root node 를 기준으로 node 순서대로 삽입
        for (int i = 1; i < n; i++) {
            insertNode(root, nodes[i]);
        }

        preorder(root); //전위 순회
        postorder(root); //후위 순회

        int[][] answer = new int[2][n];
        for (int i = 0; i < n; i++) {
            answer[0][i] = preorderList.get(i);
            answer[1][i] = postorderList.get(i);
        }
        
        return answer;
    }


    private void insertNode(Node parent, Node child) {
        if (child.x < parent.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);
            }
        }
    }


    //전위 순회
    private void preorder(Node node) {
        if (node == null) return;
        preorderList.add(node.idx); //현재노드 방문
        preorder(node.left); //왼쪽 자식 방문
        preorder(node.right); //오른쪽 자식 방문
    }

    //후위 순회
    private void postorder(Node node) {
        if (node == null) return;
        postorder(node.left); //왼쪽 자식 방문
        postorder(node.right); //오른쪽 자식 방문
        postorderList.add(node.idx); //현재노드 방문
    }
}

[Rewind]

1. 어려웠던 점

- 배열 정렬에 람다식을 이용하는 방식이 한번에 이해가 되지 않았다.

- 전위 / 후위 탐색 방식을 쉽게 알지 못하였다.

 

2. 알게된 점

- 이진 트리 구조에 대해 다시 라와인드 하게 되었다.

- 정렬 방식을 조정하는 것에 대해 알게 되었다.

 

3. 개선 방안

- 별도 클래스를 만드는 것에 어려움을 겪었던 지난 문제들과 달리, 이번 문제에선 별도 클래스를 적극적으로 만들어서 문제를 해결하였다. 

- 배열 정렬에 람다식을 이용하는 방식에 대해 학습이 필요하다.