쿼드 트리 압축하기

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

1992번: 쿼드트리

 

입력

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

출력

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

예제 입력 1 복사

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 복사

((110(0101))(0010)1(0001))

 

 

public static void main(String[] args) {

    String[] src = {
            "11110000",
            "11110000",
            "00011100",
            "00011100",
            "11110000",
            "11110000",
            "11110011",
            "11110011"
    }; // ((110(0101))(0010)1(0001))
    zipTree(src);

    src = new String[]{
            "00000000",
            "00000000",
            "00001111",
            "00001111",
            "00011111",
            "00111111",
            "00111111",
            "00111111"
    }; // (0(0011)(0(0111)01)1)
    zipTree(src);


}

public static void zipTree(String[] src) {

    String [][] input = new String[src.length][];
    for(int i=0; i<src.length; i++) {
        input[i] = new String[src.length];
        for(int j=0; j<src[i].length(); j++) {
            input[i][j] = String.valueOf(src[i].charAt(j));
        }
    }

    System.out.println(zipTree(input, 0, 0, src.length));
}

public static String zipTree(String [][] input, int x, int y, int length) {
    if(length < 2) {
        return input[y][x];
    }

    int mid = length / 2;
    int midX = x + mid;
    int midY = y + mid;

    String upperLeft = zipTree(input, x, y, mid);
    String upperRight = zipTree(input, midX, y, mid);
    String lowerLeft = zipTree(input, x, midY, mid);
    String lowerRight = zipTree(input, midX, midY, mid);

    if(upperLeft.equals(upperRight)
            && upperLeft.equals(lowerLeft)
            && upperLeft.equals(lowerRight)) {
        return upperLeft;
    }

    return new StringBuilder("(")
            .append(upperLeft)
            .append(upperRight)
            .append(lowerLeft)
            .append(lowerRight)
            .append(")").toString();
}