[Java] 백준 1992번 : 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

[문제]

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

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

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

 

[출력]

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

[예제 입력]

[풀이 과정]

 이 문제를 풀기전에 [2630번 : 색종이 만들기 https://www.acmicpc.net/problem/2630] 를 풀어봤다면 쉽게 풀었을것이다. 재귀와 분할 정복으로 풀어 보았다.

 

1) 2차원 배열에 입력값을 저장한다.

2) 영상의 맨 첫 번째 값(왼쪽 맨 위의 칸)을 기준으로  (1은 black 0은 white) 나머지 칸들이 첫 번째 값과 같은지 검사한다.

3) 모두 같았다면 첫 번째 칸의 색 번호를 sb.append()한다. 

4) 그렇지 않고 다르다면 영상을 4개의 영역으로 나누어야한다. 나누어질때는 '(' 를 넣어야한다.  영상의 크기 (N)/2를 하고 2)의 과정을 잘린 4개의 구역에서 실행한다. 이 때 나누게 될 사분면의 첫 번째 칸의 좌표와 2등분된 크기를 넘긴다.

5) 4)의 수행을 완료하였다면 ')'를 넣음으로써 끝을 알려주면 된다.

 

*쿼드트리란? (Quad Tree) :쿼드트리는 각 내부 노드에 정확히 4개의 자식 이 있는 트리 데이터 구조 이다. 쿼드트리는 옥트리 의 2차원 아날로그이며 2차원 공간을 4개의 사분면 또는 영역으로 재귀적으로 세분화하여 2차원 공간을 분할하는 데 가장 자주 사용된다. (출처 :https://en.wikipedia.org/wiki/Quadtree)

 

[코드]

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

//쿼드 트리  (재귀,분할)
public class Main {

    static  int [][]square ;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 한 변의 길이

        square = new int[N][N]; //2차원 배열

        for (int i = 0 ;  i  < N ; i ++){ //2차원 배열에 값 넣기
            String str = br.readLine();
            for (int j = 0 ; j < N; j++){
                square[i][j]= str.charAt(j)-'0';
            }
        }

        QuadTree(0,0,N);
        System.out.print(sb);
    }

    public static void QuadTree(int x, int y, int N) {

        if( checkSquare(x,y,N)){//압축가능하면 그 색의 숫자로 저장한다.
            sb.append(square[x][y]);
            return;
        }

        int divSize = N/2; //압축이 안되는 경우는 변의 길이를 절반으로 나누어 주어야한다.

        //분할
        // 분할 과정에 들어가는 경우 '(' 를 해준다
        sb.append('(');
        QuadTree(x,y,divSize); //왼쪽 위
        QuadTree(x,y+divSize,divSize); //오른쪽 위
        QuadTree(x+divSize,y,divSize); //왼쪽 아래
        QuadTree(x+divSize,y+divSize,divSize); //오른쪽 아래

        //끝났을 경우에는 ')'를 해야한다.

         sb.append(')');

    }

    public static boolean checkSquare (int x, int y, int N){ //해당하는 정사각형이 같은색으로 차 있는지 확인

        int firstBlock = square[x][y]; // 첫 번째칸의 (왼쪽 맨위) 색을기준으로 나머지 칸들이 색이 같은지 확인

        for(int i = x; i<x+N;i++){
            for(int j = y ; j < y+N;j++){
                if(firstBlock!=square[i][j]){
                   return  false; //같이 않으면 false
                }
            }
        }
        return  true;
    }
}

 

[결과]