쿼드트리란?

트리의 자식 노드가 4개인 트리를 뜻하고 있다.

3D 데이터를 표현하기 위한 자료구조를 '장면 그래프( Scene Graph )'라고 부르는데, 이도 역시 그에 포함된다.

쿼드 트리는 일반적으로 상하 개념이 없어서 3차원 세계를 4개의 평면으로 분할하지만,

정의 : 공간을 재귀적인 호출로(Recursive ) 4개의 자식 노드로 분할하는 방법

지형으로 설명을 하자면

초기에 하나의 넓은 월드의 지형을 1/4 로 나눈다.

그렇게 나온 4개의 노드를 부모로서 다시 1/4로 각각을 나눈다.

그럼 초기 하나의 월드에는 현재 16개의 노드가 존재한다.

이런 식으로 재귀적인 호출을 통해 각 노드간의 간격이 1보다 작거나 같을 때까지 분할한다.

백준 1992 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_1992 {
    static int N;
    static int[][] board;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        for(int i = 0; i < N; i++){
            s = br.readLine();
            for(int j = 0; j < N; j++){
                board[i][j] = s.charAt(j) - '0';
            }
        }
        partition(0,0,N);
        System.out.println(sb);
    }

    public static void partition(int row, int col, int size){

        if(checkNumber(row, col, size)){
            if(board[row][col] == 0) sb.append("0");
            else sb.append("1");
            return;
        }

        int newSize = size / 2;

        sb.append("(");

        partition(row, col, newSize);
        partition(row, col + newSize, newSize);
        partition(row + newSize, col, newSize);
        partition(row + newSize, col + newSize, newSize);

        sb.append(")");

    }

    public static boolean checkNumber(int row, int col, int size){
        int color = board[row][col];
        for(int i = row; i < row + size; i++){
            for(int j = col; j < col + size; j++){
                if(board[i][j] != color) return false;
            }
        }
        return true;
    }
}