백준
#백준_1992 쿼드트리 - Java
ukyonge
2020. 1. 11. 20:03
# 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;
}
}