쿼드트리 quadtree

쿼드트리 (quad.cpp)

 

문제

---

그림 과 같은 이진 이미지는 0 혹은 1 로 자료를 표현한다.

그림(b) 는 그림(a) 를 나타내는 배열을 나타낸다. 그림(b) 의 이진 이미지를 저장하기 위해 일명 쿼드트리 구조를 사용한다.

쿼드 트리는 NN 배열을 N/2 N/2 크기로 4 등분 했을 때 모두 같은 값을 가지지 않는다면, 다시 N/2 * N/2 배열에서 같은 이진 값을 가지지 않는다면 다시 .....

이런 식으로 진행하다 4 등분 된 값이 모두 같은 값을 가지면 확장이 종료된다.

그림(c) 는 쿼드 트리의 확장이 종료된 후의 배열이 모습이다.

그림(a) 에 있는 이진 이미지를 저장하지 않고 , 그림(c) 로 부터 엔코드된 그림(d) 처럼 쿼드 트리로 이미지를 저장한다.

그림(d) 에서 각 노드는 그림(c) 에 있는 배열을 나타낸다. 루트노드는 원래 배열을 나타내는 트리에 있는 각 노드의 값이 1 이면 이 때 대응되는 배열의 4 개의 작은 배열로 분할 되는 것을 의미한다.

0 이면 , 노드는 한 쌍의 값을 가진다. 이는 대응되는 배열이 더 이상 분해되지 않는다는 것을 의미 한다. 이 경우 , 두 번째 값은 0 이면 배열에 있는 모든 값이 0 , 1 이면 배열의 모든 값이 1 을 의미한다.

2(a) 의 이진 이미지를 저장하는 대신 그림(d) 의 트리를 저장하면 된다.

그림(d) 의 트리를 저장하는 방법은 따라오는 그림 에 의해서 표현될 수 있다: 이진 이미지 (a) , 이 것의 배열 표현 (b) , 이 것은 쿼드 트리 분할 (c) , 이 것의 쿼드 트리 표현 (d).

code: (1)(0,0)(1)(0,1)(1)(0,0)(0,1)(1)(0,0)(0,0)(0,0)(0,1)(0,1)(0,0)(0,1)(0,0)(0,1). 이 코드는 루트에서 리프노드로 그리고 각 레벨에서 왼쪽에서 오른쪽으로 단지 노드의 값의 리스트이다. 괄호와 콤마를 없애면, 이진 수 100101100011000000010100010001 를 얻을 수 있고 , 이것의 16 진 표현은 258C0511 이다.

우리가 해야 할 일은 주어진 이미지에서 대응되는 16 진 값을 구하는 것이다.

 

입력

---

첫 수는 양의 정수 N 이다. N * N 이진 이미지를 의미하고 N <= 512 이고 , N = 2^i 인 i 인 양의 정수 i 가 존재한다. 다음 N 줄에는 N 개의 0 혹은 1 의 이진 이미지가 입력된다.

 

출력

---

16 진수 형태로 출력한다.  

예제 입력

2
0 0
0 0

예제 출력

0

 

예제 입력

8
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

예제 출력

258C0511

코드

//쿼드트리

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

  public static ArrayList<Integer> box = new ArrayList<>();
  public static String result = "";
  public static int[][] c;
  public static int count = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    //총 몇개의 숫자를 입력 받을 것인지
    int a;
    int[][] b;

    Queue<int[]> q = new LinkedList<>();


    a = sc.nextInt();
    c = new int[a + 1][a + 1];

    for (int i = 1; i <= a; i++) {
      for (int j = 1; j <= a; j++) {
        c[i][j] = sc.nextInt();
      }
    }

    sc.close();
    quadTree(1, a, 1, a, q);
    System.out.println(Integer.toHexString(Integer.parseInt(result, 2)).toUpperCase());


  }

  public static void quadTree(int a, int a2, int b, int b2, Queue<int[]> q) {

    int[] data = new int[]{a, a2, b, b2};

    q.offer(data);

    fullWhile:
    while (!q.isEmpty()) {
      data = q.poll();
      a = data[0];
      a2 = data[1];
      b = data[2];
      b2 = data[3];

      int num = c[a][b];

      for (int i = a; i <= a2; i++) {
        for (int j = b; j <= b2; j++) {
          if (num != c[i][j]) {
            result += 1;
            q.offer(new int[]{a, a + ((a2 - a)) / 2, b, b + ((b2 - b) / 2)});
            q.offer(new int[]{a, a + ((a2 - a)) / 2, b + ((b2 - b) / 2) + 1, b2});
            q.offer(new int[]{(a + ((a2 - a)) / 2) + 1, a2, b, b + ((b2 - b) / 2)});
            q.offer(new int[]{(a + ((a2 - a)) / 2) + 1, a2, b + ((b2 - b) / 2) + 1, b2});
            continue fullWhile;
          }
        }
      }

      result += "0" + num;

    }


  }


}