[백준] 1992 쿼드트리 (JAVA)

문제 링크:

1992번: 쿼드트리

 

문제:

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

출력:

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

 

 

문제 이해:

이 문제를 처음 봤을때는 무슨 소리인지 이해가 가지 않았지만. 예시를  계속 확인하며 이해했다.

이는 하나의 정사각 행렬이 모두 같지 않다면 1,2,3,4분면으로 분할하고 이를 모든 원소가 같아질때 까지 반복하는것이었다.

아래 그림으로 예시를 들어보자.

1. (1) 전체 영역 검사 (빨간 선)
   → 전체가 같은 값이 아니므로 4등분 시작.
2. (2) 왼쪽 위 영역 검사 (파란색 원)
   → 전부 0 → 압축 가능 → 0
3. (3) 2사분면은 한번더 분할이 필요하기에 다시 4등분
   (4)초록색 원 (0 0 1 1) 출력
4. (5) 왼쪽 아래 영역 검사 
   → 0과 1이 섞여 있음 → 다시 4등분
5. (6) 왼쪽 아래 4분할 후 (7)2사분면은 한번더 분할이 필요하여 분할
   → (0(0111)01)
6. (8) 오른쪽 아래 영역 검사 (갈색 원)
   → 전부 1 → 압축 가능 → 1
7. (8) 최종 결과 조합
   → 괄호로 묶어서 (0(0011)(0(0111)01)1)

이를 재귀적으로 같아질때 까지 반복하면 구현할 수 있다.

즉 정답 코드는 다음과 같다.

 

정답 코드:

import java.awt.geom.QuadCurve2D;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    static int[][] matrix;
    static StringBuilder sb=new StringBuilder();


    //분할한 영역이 모두 같은지 확인
    public static boolean allSame(int startX,int startY, int size){
        for(int i=startX; i< startX+size;i++){
            for(int j=startY; j<startY+ size;j++){
                if(matrix[startX][startY]!=matrix[i][j]) return false;
            }
        }

        return true;
    }

    public static void QuadTree(int startX,int startY, int size){
        if(allSame(startX,startY,size)){
            sb.append(matrix[startX][startY]);
            return;
        }

        int newSize= size/2;
        sb.append('(');

        //쿼드 트리 4갈래로 분할

        //1사분면
        QuadTree(startX,startY,newSize);
        //2사분면
        QuadTree(startX,startY+newSize,newSize);
        //3사분면
        QuadTree(startX+newSize,startY,newSize);
        //4사분면
        QuadTree(startX+newSize,startY+newSize,newSize);

        sb.append(')');
    }



    public static void main(String[] args) throws IOException {
        int matrixSize;

        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        matrixSize = Integer.parseInt(br.readLine());

        matrix = new int[matrixSize][matrixSize];

        //행렬 입력
        for (int i = 0; i < matrixSize; i++) {
            String input= br.readLine();
            for (int j = 0; j < matrixSize; j++) {
                matrix[i][j] = Integer.parseInt(input.charAt(j)+"");
            }
        }

        //쿼드트리 탐색 시작
        QuadTree(0,0,matrixSize);


        //결과 출력
        System.out.println(sb.toString());

    }
}

 

 

 

마무리하며:

이는 분할정복 개념이 있어야 풀 수 있는 문제이다. 따라서 Divide and Conquer 방식을 공부한 후 구현해보길 추천한다.
특히, 영역을 나누고 나서 재귀적으로 처리하는 사고방식에 익숙해지는 것이 중요하다.
처음에는 복잡해 보일 수 있지만, 쿼드트리는 기본 구조만 이해하면 코드는 이해한 그대로 작성하면 되기에 간단하다.

 

감사합니다.