[Java] 백준 1992 : 쿼드트리

 

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

1992번: 쿼드트리

---

쿼드를 압축하는 방법은 간단하다. 

가지고 있는 모든 수가 같을 때, 같은 수로 압축을 하면 된다. 

예를 들어, 

이렇게 주어졌을 때, 

위 배열을 하나의 덩어리로 보았을 때 모든 수가 같지 않다. 그래서 압축을 할 수 없다.

압축을 하지 못하면 사이즈를 행, 열을 반으로 나누어 살펴본다. 

이렇게 4개로 나누었을 때  각각을 하나의 덩어리로 보면 같은 수로만 이루어진 부분이 있다. 이는 압축을 해주면 된다. 

이걸 나누어 지지 않을 때까지 반복하면 

이렇게 압축해 줄 수 있다. 

이걸 문제에서 요구하는 대로 (0(0011)(0(0111)01)1) 로 표현하면 된다. 

 

왼쪽에서 오른쪽으로, 위에서 아래로 이동하면서 압축해주면된다. 

 

---

import java.io.*;

public class Main {
	
	static int[][] arr;
	static int N;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		arr= new int[N][N];
		for(int i=0;i<N;i++) {			
			String[] str = br.readLine().split("");
			for(int j=0;j<N;j++) {
				arr[i][j]=Integer.parseInt(str[j]);
			}
		}
		
		quad(0,0,N);	//전체를 확인
		System.out.println(sb);
	}// main()
	
	static void quad(int startX,int startY,int len) {
		if(check(startX,startY,len)) {	//모두 같은 수로 이루어져 있으면 
			sb.append(arr[startX][startY]);	//해당 수를 출력
			return;
		}
		
		len /=2;	//사이즈를 점차 반으로 줄여가면서 확인 
		sb.append("(");	//압축의 시작
		//왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로
		quad(startX,startY,len);
		quad(startX,startY+len,len);
		quad(startX+len,startY,len);
		quad(startX+len,startY+len,len);
		sb.append(")");	//압축의 끝 
		
	}//quad()
	
	public static boolean check(int x, int y,int len){
        for(int i=x;i<x+len;i++){
            for(int j=y;j<y+len;j++){
                if(arr[x][y]!=arr[i][j])    return false;
            }
        }
        return true;
    }//check()
	
}// class Main