6-10: 쿼드트리

쿼드트리 (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.Scanner;

public class quad {

    /**
     *
     * 문제: 그림 과 같은 이진 이미지는 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 진 값을 구하는 것이다.
     *
     *
     * 입력:
     *
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     * 2
     * 0 0
     * 0 0
     *
     * 예제 출력:
     * 0
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        boolean[][] arr = new boolean[N][N];
        for (int i=0; i<arr.length;i++){
            for (int j=0; j<arr.length; j++){
                arr[i][j] = sc.nextInt() == 1;
            }
        }

        //construct quad graph representation

        Node root  = constructAndAttachNodes(arr);

        //conduct bfs and print value.
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        StringBuilder sb= new StringBuilder();
        while (!queue.isEmpty()){
            Node node = queue.remove();
            sb.append(node.data[0]);
            if (node.data[0] == 0){
                sb.append(node.data[1]);
            }

            if (node.child != null){
                for (int i=0; i<node.child.length; i++){
                    queue.add(node.child[i]);
                }
            }
        }

        //use stringbuilder output in binary to convert to hex
        String binary = sb.toString();
        String result ="";
        //get last 4 chars and convert to hex.
        while (binary.length() > 4){
            char hexDigit = convertToHex(binary.substring(binary.length()-4, binary.length()));
            result = hexDigit+result;
            binary = binary.substring(0, binary.length()-4);
        }
        char hexDigit = convertToHex(binary);
        result = hexDigit+result;

        System.out.println(result);
    }

    private static char convertToHex(String substring) {

        if (substring.length() < 4){
            int zerosToAdd = 4-substring.length();
            for (int i=0; i<zerosToAdd; i++){
                substring = "0" + substring;
            }
        }

        if (substring.equals("0000")){
            return '0';
        }
        if (substring.equals("0001")){
            return '1';
        }
        if (substring.equals("0010")){
            return '2';
        }
        if (substring.equals("0011")){
            return '3';
        }
        if (substring.equals("0100")){
            return '4';
        }
        if (substring.equals("0101")){
            return '5';
        }
        if (substring.equals("0110")){
            return '6';
        }
        if (substring.equals("0111")){
            return '7';
        }
        if (substring.equals("1000")){
            return '8';
        }
        if (substring.equals("1001")){
            return '9';
        }
        if (substring.equals("1010")){
            return 'A';
        }
        if (substring.equals("1011")){
            return 'B';
        }if (substring.equals("1100")){
            return 'C';
        }if (substring.equals("1101")){
            return 'D';
        }if (substring.equals("1110")){
            return 'E';
        }if (substring.equals("1111")){
            return 'F';
        }
        return '!';

    }

    private static Node constructAndAttachNodes(boolean[][] arr) {
        //divide arr into 4.
        if (haveToDivide(arr)){

            boolean[][][] results = divideIntoFourArrays(arr);
            //insert 1 node. latter value of int arr doesnt matter.
            Node node = new Node(new int[]{1,100});
            //add children
            Node[] children = new Node[]{
                    constructAndAttachNodes(results[0]),
                    constructAndAttachNodes(results[1]),
                    constructAndAttachNodes(results[2]),
                    constructAndAttachNodes(results[3])
            };
            node.child = children.clone();
            return node;
        } else {
            //no need to divide. insert 0 node

            Node node;

            if (!arr[0][0]){
                node = new Node(new int[]{0,0});
            } else {
                node = new Node(new int[]{0,1});
            }
            node.child = null;
            return node;
        }
    }

    public static boolean haveToDivide(boolean[][] arr){

        if(arr.length==1 && arr[0].length==1) return false;

        //if all same, then return false,
        boolean base = arr[0][0];
        for (int i= 0; i<arr.length; i++){
            for (int j=0; j<arr[0].length; j++){
                if (arr[i][j] != base) return true;
            }
        }
        return false;
    }

    public static boolean[][][] divideIntoFourArrays(boolean[][] arr){
        //if all same, then return false,
        boolean[][][] results = new boolean[4][arr.length/2][arr[0].length/2];
        for (int i= 0; i<arr.length; i++){
            for (int j=0; j<arr.length; j++){
                int mid = arr.length/2;
                if (i < mid && j < mid){
                    results[0][i][j] = arr[i][j];
                } else if (i<mid && j>=mid){
                    results[1][i][j-mid] = arr[i][j];
                } else if (i>=mid && j<mid){
                    results[2][i-mid][j] = arr[i][j];
                } else if (i>=mid && j>=mid){
                    results[3][i-mid][j-mid] = arr[i][j];
                }
            }
        }

        return results;
    }

    public static class Node{
        int[] data;
        Node[] child;

        public Node(int[] data){
            this.data = new int[2];
            this.data[0] = data[0];
            this.data[1] = data[1];
            child = new Node[4];
        }
    }
}