[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)"로 표현된다.

 

 

문제 풀이 

 

쿼드 트리 

[알고리즘] 쿼드트리(Quad Tree)란? + (백준 1992 쿼드트리) (tistory.com)

[알고리즘] 쿼드트리(Quad Tree)란? + (백준 1992 쿼드트리)

 

- 트리의 자식 노드가 4개인 트리 

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

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

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

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

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

 

[백준] 1992번 : 쿼드트리 - JAVA[자바] (tistory.com)

[백준] 1992번 : 쿼드트리 - JAVA[자바]

 

- 압축하기 위해서는 부분 영역이 모두 같은 색상이어야 한다. 

- 즉 흰색(0)으로 이루어져 있거나, 검은색(1)로 이루어진 단일 색상 영역이어야 한다는 것이다.

- 쿼드트리 방식으로 공간을 4분할 

 

정답 

 

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

public class Main {
    static int board[][];
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args)throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        board = new int[n][n];
        
        for(int i=0; i<n; i++)
        {
        	char input[] = br.readLine().toCharArray();
        	for(int j=0; j<n; j++)
        	{
        		board[i][j] = input[j]-'0';
        	}
        }
        
        partition(0,0,n);
        bw.write(sb+"");
        
        bw.flush();
        bw.close();
    }
    
    static void partition(int row, int col, int size)
    {
    	//압축이 가능할 경우 하나의 색상으로 압축
        if(check(row,col,size))
        {
            sb.append(board[row][col]);
            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 check(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(color != board[i][j])
                {
                    return false;
                }
            }
        }
        
        return true;
    }
}