[문제][알고스팟] 쿼드트리 뒤집기 (QUADTREE)

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • QUADTREE
  • 10000ms
  • 65536kb
  • 6219
  • 2997 (48%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(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 을 넘지 않습니다.

출력

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

예제 입력

4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

예제 출력

w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

---

스스로 풀었는가? O
힌트를 참고했나? X

난이도 '하'의 쉬운 문제였다.
상하로 뒤집은 결과를 구해야 했기에, 일단 4개영역(1,2,3,4사분면)의 쿼드트리를 따로 분리해서 재조합할 필요가 있었다.
상하로 뒤집을 경우 기존의 2사분면 -> 1사분면 -> 3사분면 -> 4사분면이 아닌 3사분면 -> 4사분면 -> 2사분면 -> 1사분면으로 재조합해야 한다. 
x로 시작해서 분할되는 경우 재귀함수로 분할의 끝까지 탐색한 후 3사분면 -> 4사분면 -> 2사분면 -> 1사분면으로 재조합하면서 리턴하도록 했다. 즉, 현재 문자열이 x가 아닌 경우는 그대로 리턴하고 x인경우 4가지 영역을 각각 재귀호출했다.

내가 푼 소스는 아래와 같다.

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class QUADTREE {
	
	public static String str;
	public static int idx;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("D:\\sample_input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		
		for(int testCase=1; testCase<=T; testCase++) {
			
			str = br.readLine().trim();
			
			idx = 0;
			String result = recursive();
			
			bw.flush();
			bw.write( result);
			bw.write("\n");
			
		}
		
		bw.close();

	}
	
	public static String recursive() {
		
		
		char c = str.charAt(idx);
		
		if(c != 'x') {
			return c + "";
		}
		
		
		
		// 2사분면 search
		idx++;
		String str2 = recursive();
		// 1사분면 search
		idx++;
		String str1 = recursive();
		// 3사분면 search
		idx++;
		String str3 = recursive();
		// 4사분면 search
		idx++;
		String str4 = recursive();
		
		// 2 + 1 + 3  + 4 하면 뒤집은 쿼드트리가 나온다.
		
		return "x" + str3 + str4 + str2 + str1;				
		
	}

}