[BOJ] 1992 : 쿼드트리(Java)

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

---

💡풀이

영상이 같은 수로 되어있지 않다면, 2로 계속 종이를 나누어 들어가기 때문에(4분할이므로) 분할 정복 알고리즘과 재귀를 이용한다.

영상 숫자들이 같은지 확인하는 함수를 만들어준다. 만약 이때 숫자가 영상이 발견되면 N을 2으로 나누고 탐색하는 그래프의 범위를 재설정해준다. 이를 재귀를 통해 구현해주면 된다. 

정리하자면,

1. checkGraph 함수를 통해 정해진 범위(처음에는 N값) 안의 영상의 숫자들이 같은 값인지 확인한다. 
2. 만약 모두 같다면 결과를 저장하는 배열에 해당하는 영상의 값을 넣어준다. 
3. 만약 다른 종이가 발견된다면, makeNewGraph 함수를 호출하고 새로운 영상의 범위로 넘어간 것이므로 "("를 추가해주고 이 함수 안에서 N의 값을 2로 나누어 다시 checkGraph 함수를 수행해준다. 
4. makeNewGraph 함수를 모두 빠져나왔다면 해당 영상 영역에 대한 탐색이 끝난 것이므로  ")"를 추가해준다.

이때 주의할 점은 3번 과정에서 makeNewGraph의 좌표의 증가 범위는 ++i가 아닌 N/2가 되어야 한다. 그래야 각 영상의 구역에 맞게 확인할 수 있다. 

 

또한, 입력받는 부분에서 공백으로 구분되어있는 것이 아닌 11001100과 같이 입력이 공백없이 연이어 들어오기 때문에, StringTokenizer를 사용하는 것이 아니라 입력받은 문자열에 대해 split함수를 이용하여 구분해주어야 한다. 

 

전체적인 코드는 다음과 같다. 

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

public class Q1992 {
    public static int[][] graph;
    public static String result="";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        for(int i=0;i<N;++i){
            String str[] = br.readLine().split("");
            for(int j=0;j<N;++j){
                graph[i][j] = Integer.parseInt(str[j]);
            }
        }

        checkGraph(0,0,N);
        System.out.println(result);
    }

    public static void checkGraph(int x, int y, int c){
        int pivot = graph[x][y];
        for(int i=x;i<x+c;++i){
            for(int j=y;j<y+c;++j){
                if(pivot!=graph[i][j]){
                    makeNewGraph(x,y,c);
                    result += ")";
                    return;
                }
            }
        }
        result+=pivot;
    }

    public static void makeNewGraph(int x, int y, int c){
        result += "(";
        for(int i=x;i<x+c;i+=c/2){
            for(int j=y;j<y+c;j+=c/2){
                checkGraph(i,j,c/2);
            }
        }
    }
}