[알고스팟] 쿼드 트리 뒤집기 :: 늦깎이 IT

[알고스팟] 쿼드 트리 뒤집기 URL

1. 분할정복을 사용한다.

2. 예를 들어, N x N칸이 모두 흰색 혹은 검은색으로 칠해져 있는 경우 뒤집어도 똑같은 색이다.

3. 이 아이디어에서부터 1x1 칸에는 한 가지 색만 칠해져 있으므로, 뒤집어도 똑같기 때문에 기저조건을

1x1칸으로 정한다.

4. 입력으로부터 input 문자열을 받고, 이 문자열의 인덱스를 가리키는 pointer를 선언한다.

5. recursive() 메소드를 호출하면, input 문자열의 처음부터 확인한다. input 문자열의 첫글자가 w 혹은 b라면

N x N칸 모두 하나의 색으로 칠해져있다는 뜻이므로, input 그대로 정답을 출력한다.

6. input 문자열의 첫 글자가 x라면 이것을 4등분으로 나누어야 한다. 4등분으로 나누는 기준은 왼쪽위, 오른쪽위,

왼쪽아래, 오른쪽아래로 나눈다.

7. 분할한 4개의 조각들을 뒤집어줘야 하는데 이것은 왼쪽위 ↔ 왼쪽아래, 오른쪽위 ↔ 오른쪽아래를 변경한 것이다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main{
 
    static int tCase, pointer;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            pointer = -1;
            String input = br.readLine();
            System.out.println(recursive(input));
        }
    }
 
    public static String recursive(String input) {
 
        pointer += 1;
        char ch = input.charAt(pointer);
        if (ch == 'b' || ch == 'w')
            return ch + "";
 
        String leftUp = recursive(input);
        String rightUp = recursive(input);
        String leftDown = recursive(input);
        String rightDown = recursive(input);
 
        return "x" + leftDown + rightDown + leftUp + rightUp;
 
    }
}