[종만북][알고스팟] 쿼드 트리 뒤집기 - 분할정복(DivideandConquer) JAVA

출처 : 종만북 - 07 분할정복 - 7.3 쿼드 트리 뒤집기

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

algospot.com :: QUADTREE

코드설명

일반적으로 2차원 배열이 주어지고, 해당 배열을 쿼드트리로 압축하는 문제는 분할정복 및 재귀호출로 해결할 수 있습니다.

하지만, 이미 압축된 문자열을 압축해제 하는 방법은 약간 특이합니다.

'x' 일경우는 해당 칸은 압축이 된 상태이므로 4가지 분면으로 나누어 분할한뒤 정복합니다.

'b'나 'w'인 경우 해당 size만큼의 정사각형이 압축된 것으로 판단하므로 해당 칸의 size만큼 색을 칠해주면 됩니다.

 

먼저 첫번째로 해당 decompress 코드를 작성하여 하단에 작성했습니다.

 

이후에 decompressed[][] 된 쿼드트리를 뒤집은뒤 다시 compress하는 알고리즘을 작성하면 원하는대로 될 것 입니다.

하지만 이와 같은 방식은, 2^20 x 2^20 으로 된 map에서 사용하기에 너무 많은 메모리가 사용됩니다. 만약 맨 왼쪽 위에 검은 픽셀이 하나 있고 나머지는 전부 흰 픽셀이라고 한다면, 쿼드트리를 활용해 직접 decompressed[2^20][2^20]을 만들어 한다면 너무 많은 메모리가 사용됩니다.

 

이런 경우에 쓸 수 있는 방법은 압축을 해제한 결과를 메모리에 다 저장하는 대신 결과 이미지를 뒤집은 결과를 곧장 생성하는 코드를 작성합니다. 예를 들어, decompress()의 기저사례는 s.charat(index)가 'w'나 'b' 즉 흰색이나 검은색일 경우입니다. 해당 Size에서 전체가 검은색이나 흰색이라는 의미인데, 이런 경우 뒤집더라도 결과가 같습니다.

 

전체가 한 가지 색이 아닌 경우에는 재귀호출을 이용해 네 부분을 각각 상하로 뒤집은 결과를 얻은뒤, 이들을 병합해 답을 얻습니다. 뒤집힌 그림의 압축결과는 이미 존재한다 가정하고, 그렇다면 어떻게 병합해야 decompress와 compress를 한번에 수행할 수 있을지 알아보겠습니다.

 

네가지 부분문제로 반환받은 1사분면, 2사분면, 3사분면, 4사분면을

3사분면, 4사분면 1사분면, 2사분면 순으로 배치합니다.

이떄 상하반전은 이미 같은 색깔일경우 뒤집는 것은 사실상 동일하고,

상하로 뒤집는 경우는 4가지 부분문제가 다시 상위호출자에게 재배치되며 뒤집혀집니다.

코드

쿼드 트리 압축을 해제하는 재귀호출 알고리즘입니다.

 

입력 예시 1

16
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

결과 예시 1

wwwwwwwwwwwwwwbb
wwwwwwwwwwwwwwbb
wwwwwwwwwwwwbbbb
wwwwwwwwwwwwbbbb
wwwwbbbbwwwwwwww
wwwwbbbbwwwwwwww
wwwwbbbbwwwwwwww
wwwwbbbbwwwwwwww
wwbbwwwwbbbbbbbb
bbbbwwwwbbbbbbbb
wwwwwwwwbbbbbbbb
wwwwwwwwbbbbbbbb
wwwwbbbbbbbbbbbb
wwwwbbbbbbbbbbbb
wwwwbbbbbbbbbbbb
wwwwbbbbbbbbbbbb

 

압축해제 재귀호출 알고리즘입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int[] input;
	public static int index = 0;
	public static char[][] decompressed;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		decompressed = new char[N][N];
		st = new StringTokenizer(br.readLine());
		String str = st.nextToken();
		decompress(str, 0, 0, N);
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(decompressed[i][j]);
			}
			System.out.println();
		}
		
	}
	public static void decompress(String s, int y, int x, int size) {
//이 기저사례는 필요없습니다.
//siz가 1이 되는경우에도 이미 아래의 문자열에서 처리하기 때문입니다.
//		if(size == 1) {
//			decompressed[y][x] = s.charAt(index);
//			return ;
//		}
		
		//만약 'x'라면, 해당 칸은 재귀함수가 작동합니다.
		if(s.charAt(index) == 'x') {
			index++;
			int halfSize = size / 2;
			decompress(s, y, x, halfSize);
			decompress(s, y, x + halfSize, halfSize);
			decompress(s, y + halfSize, x, halfSize);
			decompress(s, y + halfSize, x + halfSize, halfSize);
		}
		else if(s.charAt(index) == 'b' || s.charAt(index) == 'w') {
			for(int i=0;i<size; i++) {
				for(int j=0; j<size;j++) {
					decompressed[y + i][x + j] = s.charAt(index);
				}
			}
			index++;
		}
		
		
		
	}
	

}

 

만약 압축해제한 코드를 map[][]에 배열해서 작동시킨다면, 아래처럼 만든뒤 상하를 바꿔서 압축하면 됩니다.

입력예시 1

2
w
xbwwb

결과예시 1

w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w
 w w w w w w w w w w w w w w w w

 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 b b b b b b b b w w w w w w w w
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b
 w w w w w w w w b b b b b b b b

 

두번쨰 압축해제하여 map에 만드는 코드입니다.

중요한점은 'x'를 만나면, 4사분면으로 나뉜다는점. 그리고 만약 'b'나 'w'라면 해당 구간은 모두 해당색깔인 것을 유의합니다. 만약 'x'를 만나면, 분할정복으로 사이즈를 바꾸면서 모든 구간을 정복해야합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static String input;
	public static int idx = 0;
	public static char[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int size = (int) Math.pow(2, N);
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			input = st.nextToken();
			map = new char[size][size];
			idx = 0;
			decompress(0, 0, size);
			for(int k=0;k<size;k++) {
				for(int j=0;j<size;j++) {
					System.out.print(" "+map[k][j]);
				}
				System.out.println();
			}
		}
	}		
	
	public static void decompress(int startR, int startC, int size) {
		//기저사례 : 만약 'b'이거나 'w'라면, 해당 startR ~ startC , Size의 구간은 모두 그 색깔입니다.
		char words = input.charAt(idx++);
		if(words == 'b' || words == 'w') {
			for(int i=0; i<size; i++) {
				for(int j=0; j<size; j++) {
					map[startR + i][startC + j] = words;
				}
			}
			
			return ;
		}
		//만약 'x'를 만난다면, 4개의 분할정복 칸으로 나뉩니다.
		else if(words == 'x') {
			int halfSize = size  / 2;
			decompress(startR, startC, halfSize);
			decompress(startR, startC + halfSize, halfSize);
			decompress(startR + halfSize, startC, halfSize);
			decompress(startR + halfSize, startC + halfSize, halfSize);
		}
		return ;
	}
	
}

 

 

decompress와 compress를 한번에 다 같이 하는 방법입니다.

일반적이라면, decompress를 한뒤 메모리를 사용해서 배열을 만든뒤 다시 compress하는 방법을 생각할텐데 이렇게 한번에 처리한다면 매우 효과적입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int[] input;
	public static int index = 0;
	public static char[][] decompressed;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());

		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			index = 0;
			System.out.println(reverseWithoutDecompressInMatrix(str));
		}
		
	}
	public static String reverseWithoutDecompressInMatrix(String s) {
		//만약 흰색이나 검은색이라면, 해당 사분면은 이미 모두 해당 색깔입니다.
		if(s.charAt(index) == 'b' || s.charAt(index) == 'w' ) {
			return String.valueOf(s.charAt(index++));
		}
		
		//만약 'x'일경우 4가지 부분문제로 분할합니다.  
		index++;
		String upperLeft = reverseWithoutDecompressInMatrix(s);
		String upperRight = reverseWithoutDecompressInMatrix(s);
		String lowerLeft = reverseWithoutDecompressInMatrix(s);
		String lowerRight = reverseWithoutDecompressInMatrix(s);
		
		return "x"+ lowerLeft + lowerRight + upperLeft + upperRight; 
		
	}
	

}