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];
}
}
}