[백준 1992] 쿼드트리

문제    www.acmicpc.net/problem/1192

풀이

( 1 ) 문제 쪼개기

기준점(x,y)과 크기(size)를 잡고

주어진  N*N 배열을 4등분한다.

- ( x , y , size/2 )           ( x+size/2 , y , size/2 ) 

  ( x , y+size/2 , size/2 ) ( x+size/2 , y+size/2 , size/2 ) 

X , Y	0	0	0	X+ SIZE/2 , Y	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	1	1	1	1
0	0	0	0	1	1	1	1
X, Y+ SIZE/2	0	0	1	X+SIZE/2 , Y+SIZE/2	1	1	1
0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1

(2) 확인하기

각각의 구역에 대해서 확인하고, 

해당 구역 내의 모든 값이 동일할 경우 그대로 출력한다.

해당 구역 내의 값이 다를 경우 (1)을 반복한다.

0				0	0	0	0
				0	0	0	0
				1	1	1	1
				1	1	1	1
0	0	0	1	1
0	0	1	1
0	0	1	1
0	0	1	1

코드

/*
 *  Coded by Handal ( 2019.02 )
 */
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader brr = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stt;
    static int[][] file;
 
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(brr.readLine());
 
        file = new int[N][N];
        for (int i = 0; i < N; i++) {
            String str = brr.readLine();
            for (int j = 0; j < N; j++)
                file[i][j] = str.charAt(j) - '0';
        }
 
        zip(0, 0, N);
    }
 
    static void zip(int x, int y, int size) {
        boolean b = true;
        int std = file[x][y];
        for (int i = x; i < x + size && b; i++)
            for (int j = y; j < y + size && b; j++)
                if (file[i][j] != std) b = false;
 
        if (b)
            System.out.print(std);
        else {
            int nS = size/2;
            System.out.print("(");
            zip(x, y, nS);
            zip(x, y + nS, nS);
            zip(x + nS, y, nS);
            zip(x + nS, y + nS, nS);
            System.out.print(")");
        }
    }
}