[Algospot] QUADTREE (분할 정복)

#. 문제 

https://algospot.com/judge/problem/read/QUADTREE

* 이 문제의 저작권은 Algospot에 있습니다.

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

- 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.

- 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.

- 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은 xwwwb로 압축됩니다.

그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.

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

[ 입력 ]

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

[ 출력 ]

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

#. 문제 해결 과정

  1. 문제를 읽고 이해하기

  2. 문제를 익숙한 용어로 재정의 + 추상화 -> 풀이

  3. 어떻게 해결할지 계획 세우기(알고리즘, 자료구조 선택) -> 풀이

  4. 계획 검증하기(수행 시간과 사용 메모리 확인)

    - 수행 시간 : 1초 이내 / 사용 메모리 : 64KB 이하

  5. 계획 수행하기

  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아보기

#. 풀이

  1. 테이스 케이스 입력

   - 조건 : C <= 50

  2. C줄의 쿼드 트리로 압축한 코드 입력

   - 조건 : 문자열 길이 <= 1,000

  3. 압축된 코드를 풀고 결과를 출력

   - 조건 : 1. 모든 코드가 검은 색일 경우 b,

             2. 흰 색일 경우 w,

             3. 같은 색이 아닐 경우 x

             4. 원본 그림의 크기 <= 220 x 220

w

xbwwb

xbwxw bbwb

xxwww bxwxw bbbww xxxww bbbww wwbb

  public void reverse(string[][] quadtree) { }

   - if 쿼드 트리의 첫 글자가 w or b 인 경우 해당 코드를 return

   - else 첫 글자가 x인 경우 나머지 부분은 4분할로 쪼개 재귀 호출

   - 결과는 뒤바뀐 결과를 즉, 1,2,3,4를 3,4,1,2 로 출력

      1 2     =>   3 4

      3 4            1 2

w

xwbbw

xxbwwbbbw

xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

#. 코드

import java.io.*;
 
public class C7_5_QUADTREE {
    public static int C, position;
    
    public static String reverse(String quadTree) {
        // quadtree의 첫 글자가 x가 아닐 경우 해당 압축 코드를 리턴
        if(quadTree.charAt(position) != 'x') {
            position++;
            return quadTree.charAt(position-1) + "";
        }
        // quadtree의 첫 글자가 x일 경우 재귀 호출 수행
        position++;
        String upperLeft = reverse(quadTree);    // 1
        String upperRight = reverse(quadTree);    // 2
        String lowerLeft = reverse(quadTree);    // 3
        String lowerRight = reverse(quadTree);    // 4
        
        // 상하로 뒤집은 결과 3,4,1,2
        return "x"+ lowerLeft + lowerRight + upperLeft + upperRight;
    }
    
    public static void run() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        /* input a test case  */
        C = Integer.parseInt(br.readLine().trim());
        assert C <= 50 : "Error :: testCase must be no more than 50.";
        
        while(C-->0) {    // start testCase
            /* input a quadTree */
            String quadTree = br.readLine().trim();
            assert quadTree.length() <= 1000 : "Error :: quadtree must be no more than 1,000.";
            
            position = 0;
            bw.write(reverse(quadTree) + "\n");
        }
        bw.close();
        
    }
    public static void main(String[] args) throws IOException{
        C7_5_QUADTREE.run();
    }
}

#. 결과

  - Input --------------------------------------------------------

4

w

xbwwb

xbwxwbbwb

xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

------------------------------------------------------------------

  - Output --------------------------------------------------------

w

xwbbw

xxbwwbbbw

xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

------------------------------------------------------------------