문제

입력

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

출력

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

입출력 예

풀이

1. 현재 사각형이 같은 문자로 이루어져 있지 않다면 현재 변의 길이 / 2의 사각형을 4개로 분할해서 다시 검사

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//백준 1992 쿼드 트리 -> 재귀
public class Main_B1992 {
	static int N;
	static int[][] arr;
	static StringBuilder sb = new StringBuilder();
	static void makeQuadTree(int x,int y,int N){
		if(check(x,y,N)) {
			sb.append(arr[x][y]);
			return;
		}
		sb.append("(");
		//왼쪽 위
		makeQuadTree(x, y, N/2);
		//오른쪽 위
		makeQuadTree(x, y+N/2, N/2);
		//왼쪽 아래
		makeQuadTree(x+N/2, y, N/2);
		//오른쪽 아래
		makeQuadTree(x+N/2, y+N/2, N/2);
		sb.append(")");
	}
	//같은 색이 나오는지 확인
	public static boolean check(int x,int y,int N) {
		int temp = arr[x][y];
		for(int i=x;i<x+N;i++) {
			for(int j=y;j<y+N;j++) {
				if(temp!=arr[i][j]) 
					return false;
			}
		}
		return true;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		char[]temp;
		for(int i=0;i<N;i++) {
			temp=br.readLine().toCharArray();
			for(int j=0;j<N;j++) {
				arr[i][j]=(int)(temp[j]-48);
			}
		}
		makeQuadTree(0,0,N);
		bw.write(sb.toString());
		bw.flush();
	}
}