길 찾기 게임

1. 문제 설명

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

2. 이론

• 이진 탐색 트리 (Binary Search Tree)

  이진 탐색 트리는 효율적인 탐색을 위해 고안된 방법이다. 이진 탐색트리는 아래의 조건을 만족하는 트리 구조이다.

1) 모든 원소는 서로 값이 다른 유일한 값을 갖는다. 2) 왼쪽 서브트리에 있는 원소는 루트 노드보다 키값이 작다. 3) 오른쪽 서브트리에 있는 원소는 루트 노드보다 키값이 크다. 4) 루트 노드는 서브 트리를 2개만 갖는다.

3. 해결 Point

이 문제는 이진 탐색 트리를 이용해 문제를 풀어야 한다.

문제의 예시를 살펴보면 x값은 이진 트리에서 위치를 의미하고, y는 레벨을 의미한다. 즉, y값이 가장 큰 노드가 이진 탐색 트리의 Root node가 될 것이다.

이를 위해서 주어진 노드를 y가 큰 순서대로 정렬한 뒤 이진 탐색 트리를 만든다.

class Node {
  int x;		// x 값
  int y;		// y 값
  int number;	// 노드 번호
  node left;	// 왼쪽 서브트리
  node right;	// 오른쪽 서브트리
}

class Tree {
  Node root; 	// 루트 노드

  void addNode(Node node) {
    if (root is null) {
      root = node;
    }

    else {
      if (node.x < root.x) {	// 루트 노드보다 x 값이 작으면
        root.left = node;	// 왼쪽 서브트리에 삽입
      }
      if (node.x > root.x) {	// 루트 노드보다 x 값이 크면
        root.right = node;	// 오른쪽 서비트리에 삽입
      }
    }
  }
  void preorder (Node node, int[] pre) {
    pre.add(node.number);
    preorder(node.left, pre);
    preorder(node.right, pre);
  }
  void postorder (Node node, int[] post) {
    postorder(node.left, post);
    postorder(node.right, post);
    post.add(node.number);
  }
}

class solution {

  int[][] solution(int[][] nodeinfo) {
    for(int i : nodeinfo.length) {
      array.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
    }
    array.sortbyY;
  }
  Tree tree = new Tree();
  for(int i : array.size()) {
    tree.addNode(array.get(i));
  }
  int[] preorder;
  int[] postorder;
  tree.preorder(tree.root, preorder);
  tree.postoder(tree.root, postorder);
}

4. Source Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Solution {

  public static ArrayList<Integer> preOrder;
  public static ArrayList<Integer> postOrder;

  public int[][] solution(int[][] nodeinfo) {
    int[][] answer = new int[2][nodeinfo.length];

    ArrayList<Node> array = new ArrayList<Node>();
    for(int i=0; i<nodeinfo.length; i++){
      array.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
    }

    Collections.sort(array, new Comparator<Node>() {
      @Override
      public int compare(Node node1, Node node2) {
        if (node1.getY() > node2.getY()) {
          return -1;
        } else if (node1.getY() < node2.getY()) {
          return 1;
        }
        return 0;
      }
    });

    Tree tree = new Tree();
    for(int i=0; i<array.size(); i++){
      tree.addNode(array.get(i));
    }

    //preOrder
    preOrder = new ArrayList<Integer>();
    tree.preOrder(tree.root, preOrder);

    //postOrder
    postOrder = new ArrayList<Integer>();
    tree.postOrder(tree.root, postOrder);

    for(int j=0; j<answer[0].length; j++){
      answer[0][j] = preOrder.get(j);
      answer[1][j] = postOrder.get(j);
    }

    return answer;
  }
}

class Node {
  int x;
  int y;
  int number;
  Node left;
  Node right;

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

  public int getY() {
    return y;
  }

  public int getX() {
    return x;
  }

  public int getNumber() {
    return number;
  }
}

class Tree {
  Node root;

  public void addNode(Node node) {
    if (root == null) {
      root = node;
    } else {
      addNode(node, root);
    }
  }

  public void addNode(Node node, Node root){
    if(node.getX() < root.getX()) {
      if(root.left == null){
        root.left = node;
      }
      else{
        addNode(node, root.left);
      }
    }
    if(node.getX() > root.getX()) {
      if(root.right == null){
        root.right = node;
      }
      else {
        addNode(node, root.right);
      }
    }
  }

  public void preOrder(Node node, ArrayList<Integer> pre) {

    if (node == null) return;

    pre.add(node.number);
    preOrder(node.left, pre);
    preOrder(node.right, pre);
  }

  public void postOrder(Node node, ArrayList<Integer> post) {

    if (node == null) return;

    postOrder(node.left, post);
    postOrder(node.right, post);
    post.add(node.number);
  }

}