[Algorithm] 🌳쿼드트리 뒤집기

0. 문제

쿼드 트리로 압축한 그림을 상하로 뒤집어서 다시 압축한 결과를 출력해라

입력
테스트 케이스(C)
쿼드 트리로 압축한 그림 문자열

출력
주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력

1. 문제 간단 해석

압축된 문자열을 제공함
이를 상하가 반대로 뒤집어서 압축한 문자열을 출력함

2. 아이디어

💡 색이 모두 같지 않으면 4가지로 쪼갬 : 분할정복, 재귀함수
💡 상하 뒤집기 : 0,1,2,3 위치를 2,3,0,1로 재배치

3. 핵심 풀이

1) 분할정복

head++;
String str[] = new String[4];
str[0] = reverse(); // 왼쪽상단
str[1] = reverse(); // 오른쪽상단
str[2] = reverse(); // 왼쪽하단
str[3] = reverse(); // 오른쪽하단

2) 상하 뒤집기

return "x"+str[2]+str[3]+str[0]+str[1];

4. 코드

import java.io.*;

public class QuadTree {
	static String s;
	static int head = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int C = Integer.parseInt(br.readLine());
		
		for(int i=0; i<C; i++) {
			head = 0;
			s = br.readLine();
			
			System.out.println(reverse());
		}
		
	}
	
	static String reverse() {
		
		if(s.charAt(head)!='x'){
			head++;
			return s.charAt(head-1)+"";
		} 
		
		// x이면 4가지 구역으로 쪼개짐
		head++;
		String str[] = new String[4];
		str[0] = reverse(); // 왼쪽상단
		str[1] = reverse(); // 오른쪽상단
		str[2] = reverse(); // 왼쪽하단
		str[3] = reverse(); // 오른쪽하단
		
		return "x"+str[2]+str[3]+str[0]+str[1];
	}

}

5. 결과

성공~