쿼드 트리 뒤집기(난이도 - 하)

1. 문제 설명

(1) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)가 있습니다.

 

(2) 쿼드 트리는 주어진 공간을 4개로 항상 분할해 재귀적으로 표현하며, (2^N) X (2^N) 크기를 가집니다.

 

(3) 쿼드 트리는 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

- 이 그림의 픽셀이 모두 검은색이라면, 압축 결과는 b가 됩니다.

- 이 그림의 픽셀이 모두 흰색이라면, 압축 결과는 w가 됩니다.

- 모든 픽셀이 같은 색이 아니라면, 압축 결과는 x가 됩니다.

 

- 이때, x는 하위 자식을 가질 수 있으며 아래와 같이 표현될 수 있습니다.

(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)

(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)

 

 

그림 상태가 안 좋다.

원을 잘 못 그린다.

( 위 예제 쿼드 트리를 해석하면 아래와 같다. )

xxwww bxwxw bbbww xxxww bbbww wwbb

 

(4) 이때, 입력받은 쿼드 트리 그림을 상하로 뒤집은 그림을 쿼드 트리 압축해서 출력하는 프로그램을 작성하시오.

 

( 위의 예제를 상하로 뒤집은 결과는 아래와 같다. )

xxwbx wwxbb wwbw bxwbw wxwww xbbwb

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 모든 문자열의 길이는 1,000이하이며, 원본 그림의 크기는 (2^20) X (2^20)을 넘지 않습니다.

 

출력 조건

(1) 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

 

 

입력 예제

4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

출력 예제

w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

 

3. 제약 조건

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

 

 

 

 

4. 가정법

(1) "x"가 나오게 되면 4분면으로 입력받기 때문에 자식노드가 4개 미만인 부모노드를 가지는

쿼드 트리는 없다고 가정한다.

 

 

 

 

5. 기저 사례

(1) 입력받는 String 배열 변수의 첫 글자가 w 또는 b인 경우이다.

 

 

 

 

6. 코드

: 두 가지의 코드가 존재하며, 아래의 설명을 보자.

 

(1)의 코드는 무식하게 접근하여 해결하는 방법을 보여준다. 그냥 단순히 재귀 호출로 압축 해제 후

다시 압축하는 것이다. 그러나, 최악의 상황의 예로 왼쪽 위 한 픽셀만  검은색이고 나머지는

흰색 부분인 경우, 감당할 수 없는 양의 데이터가 나오게 되며 제약 조건을 만족하지 못하게 된다.

 

( (1)의 코드는 압축 해제하는 과정만 보여줄 것이기 때문에, 입력 값 "xbwxwbbwb" 넣어서 확인해보자. )

 

 

그러므로 더욱 간단한 방법을 사용해야 한다. 그것은 바로간단하게 압축해제 하지 않고 입력받은 결과 이미지를

바로 뒤집은결과로 곧장 생성하는 것을 사용해야 한다. 그 방법이 (2)의 코드에서 잘 보여주고 있다.

 

 

(1) Brute-Force

public class QuadTree1 {
    private static String quadTree;
    private static char decompressed[][];
 
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
 
        quadTree = sc.readLine();
        decompressed = new char[quadTree.length()][quadTree.length()];
        decompress(quadTree, 0, 0, 0, quadTree.length()-1); 
 
        // 압축 해제한 결과를 보여주는 이중 for문
        for(int i=0; i<quadTree.length(); i++) {
            for(int j=0; j<quadTree.length(); j++) {
                System.out.printf("%2c",decompressed[i][j]);
            }
            System.out.println();
        }
        sc.close();
    }
 
    // 압축 해제를 수행하는 함수
    private static int decompress(String s, int it, int y, int x, int size) {
        char head = s.charAt(it++);
 
        // 기저사례: head의 첫 글자가 b 또는 w 인 경우
        if (head == 'b' || head == 'w') {
            for (int dy = 0; dy < size; dy++) {
                for (int dx = 0; dx < size; dx++) {
                    decompressed[y + dy][x + dx] = head;
                }
            }
        } else {
            // 네 부분을 쪼개 각각 순서대로 압축 해제한다.
            // 위에서 아래로 각각 1,2,3,4사 분면을 재귀호출한다.
            int half = size / 2;
            it = decompress(s, it, y, x, half);
            it = decompress(s, it, y, x + half, half);
            it = decompress(s, it, y + half, x, half);
            it = decompress(s, it, y + half, x + half, half);
        }
        return it;
    }
}

 

 

(2) 분할정복

 

public class QuadTree2 {
    // 현재 쿼드 트리의 값 변수
    private static String quadTree;
    // iterator 변수
    private static int it;
    // 출력을 위한 변수
    private static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int C = Integer.parseInt(sc.readLine());
 
        for(int i=0; i<C; i++) {
            quadTree = sc.readLine(); 
            it=0;
 
            sb.append(solve()+"\n");
        }
        System.out.println(sb);
    }
 
    // 쿼드 트리를 해결하는 주요 메서드
    private static String solve() {
        // 먼저 하나의 값을 받는다.
        char pick = quadTree.charAt(it++);
 
        // 기저 사례(1): black이거나 white인 경우 해당 값 리턴
        if(pick=='b' || pick=='w') {
            return pick+"";
        }
 
        // x를 받는 기준으로 분할 시작하며
        // 각각 3,4,1,2 사분면을 뜻한다.
        String q3 = solve();
        String q4 = solve();
        String q1 = solve();
        String q2 = solve();
 
        return "x"+q1+q2+q3+q4;
    }
}

 

 

7. 시간 복잡도 분석

- reverse()는 문자열 하나에 한 번 호출됩니다.

 

- 그러므로 호출되는 수는 문자열의 길이에 비례하므로 O(N)이 됩니다.

 

- 또한 각 문자열을 합치는 데 O(N)의 시간이 됩니다.

 

 

8. 추가로 풀어보면 좋은 문제

1992번: 쿼드트리 (acmicpc.net)

1992번: 쿼드트리