#백준_1992 쿼드트리 - Java

# https://ukyonge.tistory.com/21 문제와 같이 분할 정복 문제로써 행렬을 나누어 진행하면 됨 

https://ukyonge.tistory.com/21에서는 9개로 분할하였지만, 이 문제에서는 4개로 분할하여 해결

package bj;

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

public class p1992 {
	static int arr[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<N; j++) {
				arr[i][j] = (str.charAt(j)-'0');
			}
		}
		solve(N,0,0);
		
		
	}
	
	public static void solve(int n, int x, int y) {
		if(n==1) {
			System.out.print(arr[y][x]);
			return;
		}
		
		if(check(n, x, y)) {
			System.out.print(arr[y][x]);
		}else {
			int div = n/2;
			System.out.print('(');
			solve(div, x, y);
			solve(div, x+div, y);
			solve(div, x, y+div);
			solve(div, x+div, y+div);
			System.out.print(')');
		}
	}
	
	public static boolean check(int n, int x, int y) {
		
		int val = arr[y][x];
		
		boolean rs=true;
		
		for(int i=y; i<y+n; i++) {
			for(int j=x; j<x+n; j++) {
				if(val != arr[i][j]) {
					rs = false;
					return rs;
				}
			}
		}
		
		return rs;
	}
}