7.2 쿼드 트리 뒤집기

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 기법 중 하나
—> 쿼드 트리 (quad tree)
주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙음.

문제

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

시간 및 메모리 제한

프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 ㅎ바니다.

입력

첫 줄에 테스트 케이스의 개수 C(C는 50보다 작거나 같음)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 2^20 * 2^20 을 넘지 않습니다.

출력

각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

예제 입력

4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

예제 출력

w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

압축 문자열 분할하기

    static char[][] decompressd = new char[Integer.MAX_VALUE][Integer.MAX_VALUE];

    public static void decompress(String s, int pos, int y, int x, int size) {
        // 한 글자를 검사할 때마다 포인터 역할을 하는 변수를 한 칸 앞으로 옮긴다.
        char cur = s.charAt(pos);
        pos++;
        // 기저 사례 : 첫 글자가 b 또는 w인 경우
        if(cur == ‘b’ || cur == ‘w’) {
            for (int dy = 0 ; dy < size ; ++dy) {
                for (int dx = 0 ; dx < size ; ++dx) {
                    decompressd[y+dy][x+dx] = cur;
                }
            }
        }
        else {
            // 네 부분을 각각 순서대로 압축 해제한다.
            int half = size/2;
            decompress(s, pos, y, x, half);
            decompress(s, pos, y, x+half, half);
            decompress(s, pos, y+half, x, half);
            decompress(s, pos, y+half, x+half, half);
        }

    }

압축 다 풀지 않고 뒤집기

    static int pos;

    public static String reverse(String s) {
        char cur = s.charAt(pos);
        pos++;
        if (cur == 'b' || cur == 'w') return cur + "";
        String upperLeft = reverse(s);
        String upperRight = reverse(s);
        String lowerLeft = reverse(s);
        String lowerRight = reverse(s);
        // 위와 아래 조각들 위치를 바꾼다.
        return "x" + lowerLeft + lowerRight + upperLeft + upperRight;
    }

pos는 전역 변수로서 계속 값이 증가하므로 나누어야 하는 조각들에 대해 계속 나눠 나가다가 b or w를 만나면 단순히 return해주기만 하면 된다!

#책/종만북#