[프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT) - Java

문제

길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT)

아이디어

1. 먼저 주어진 노드들을 y좌표 내림차순, x좌표 오름차순으로 정렬한다. (루트 노드의 y좌표가 가장 크기 때문)

   Arrays.sort(node, (n1, n2) -> {
        if (n1.y == n2.y) return n1.x - n2.x;
        return n2.y - n1.y;
    });
   

2. 정렬된 노드들을 바탕으로, 루트 노드부터 시작해서 재귀를 통해 트리 정보를 구성한다.
   부모 노드와 자식 노드의 x좌표를 비교해서 왼쪽 자식으로 넣을지, 오른쪽 자식으로 넣을지 분기한다.
   이 때 들어갈 곳에 이미 다른 노드가 있다면 (들어갈 위치의 자식 노드가 null이 아니라면), 그 자식 노드 아래로 넣어야하므로 재귀 호출한다.

   public 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);
        }
    }
   }
   

3. 전위 순회, 후위 순회를 수행하며 답을 저장한다.

전체 코드

import java.util.*;

class Solution {
    
    int[][] answer;
    int idx;
    
    class Node {
        int x;
        int y;
        int v;
        Node left;
        Node right;
        
        public Node(int x, int y, int v, Node left, Node right) {
            this.x = x;
            this.y = y;
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }
    
    public 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);
            }
        }
    }
    
    public void preorder(Node root) {
        if (root != null) {
            answer[0][idx++] = root.v;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            answer[1][idx++] = root.v;
        }
    }
    
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        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);
        }
        
        Arrays.sort(node, (n1, n2) -> {
                if (n1.y == n2.y) return n1.x - n2.x;
                return n2.y - n1.y;
            });
        
        Node root = node[0];
        for (int i=1; i<node.length; i++) {
            insertNode(root, node[i]);
        }
        
        idx = 0;
        preorder(root);
        idx = 0;
        postorder(root);
        
        return answer;
    }
}