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

프로그래머스

---

코드

import java.util.*;

class Solution {
    static class Node {

        private final int num;
        private final int x;
        private final int y;

        private Node leftChild;
        private Node rightChild;

        public Node(int num, int x, int y) {
            this.num = num;
            this.x = x;
            this.y = y;
            this.leftChild = this.rightChild = null;
        }
    }

    public int[][] solution(int[][] nodeinfo) {
        List<Node> nodeList = new ArrayList<>();

        // Node 초기화
        int i = 1;
        for (int[] node : nodeinfo)
            nodeList.add(new Node(i++, node[0], node[1]));

        // Tree 빌드
        nodeList.sort(comparator);
        for (i = 1; i < nodeList.size(); i++)
            addNode(nodeList.get(0), nodeList.get(i));

        // 전위, 후위 처리
        preOrder(nodeList.get(0));
        postOrder(nodeList.get(0));

        return new int[][]{pre.stream().mapToInt(Integer::intValue).toArray(), post.stream().mapToInt(Integer::intValue).toArray()};
    }

    void addNode(Node parent, Node child) {
        if (parent.x > child.x) {
            if (parent.leftChild == null)
                parent.leftChild = child;
            else
                addNode(parent.leftChild, child);
        }
        else {
            if (parent.rightChild == null)
                parent.rightChild = child;
            else
                addNode(parent.rightChild, child);
        }
    }

    List<Integer> pre = new ArrayList<>();
    List<Integer> post = new ArrayList<>();

    void preOrder(Node n) {
        pre.add(n.num);
        if (n.leftChild != null) preOrder(n.leftChild);
        if (n.rightChild != null) preOrder(n.rightChild);
    }

    void postOrder(Node n) {
        if (n.leftChild != null) postOrder(n.leftChild);
        if (n.rightChild != null) postOrder(n.rightChild);
        post.add(n.num);
    }

    Comparator<Node> comparator = (o1, o2) -> {
        if (o1.y == o2.y)
            return o1.x - o2.x;
        return o2.y - o1.y;
    };
}

 

풀이

 

1. 트리 빌딩
   • 기존 트리 빌딩 방식
     :  노드를 트리에 추가한 후 노드의 우선 순위에 따라 트리를 정렬하며 추가, 정렬을 반복한다
   • 사용할 트리 빌딩 방식
     :  노드를 우선순위 순으로 정렬 후, 가장 우선 순위가 높은 노드를 루트로 기준 삼고 차례대로 노드를 추가한다
2. 노드의 우선 순위
   
   • 문제 조건
     y 좌표 : 노드의 Level
     x 좌표 : 노드의 위치
     
     
   • 우선순위 정렬 (Comparator 사용 - 객체 간 비교)
     1. y값이 작은 순으로 정렬
     2. y값이 같은 경우, x값이 작은 순으로 정렬
3. 노드 추가 방식 의사 코드    
   1.     func ( parent, node ) {
          if ( node.x is parent's left sub tree )
              if ( parent.leftChild is not current )
                  add node
              else
                  func ( parent.leftChild, node )
          else ( node.x is parent's right sub tree )
              if ( parent.rightChild is not current )
                  add node
              else
                func ( parent.rightChild, node )
      }

 

• 순회 방식 의사 코드
  • 전위
    
    •       func ( node ) {
          visit ( node )
          func ( node.leftChild )
          func ( node.rightChild )
      }
  • 후위
    
    •       func ( node ) {
          func ( node.leftChild )
          func ( node.rightChild )
          visit ( node )
      }
• 개선점
      List 만 사용해보다 보니 배열에 익숙치 않아 반환을 위한 형 변환 시 막혔음, 개선 필요