백준[자바]_1992_쿼드트리_분할정복

오늘은 색종이 문제에 이어서 두 번째로 분할정복의 문제를 풀이했다. 이번 문제는 쿼드트리를 생각해보는 문제로 트리의 개념이 직접적으로 코드에 구현되지는 않지만, 한 번쯤 생각해볼만한 문제이다.

우리가 평소에 알고 있던 트리는 이진트리로서 한 노드가 가질 수 있는 자식노드가 최대 2개인 트리의 구조이다. 그렇다면 쿼드 트리는 무엇일까? 말 그대로 한 노드가 가질 수 있는 자식 노드가 최대 4개인 트리의 구조이다. 그림상으로 보면 다음과 같다.

 그렇다면 이 문제에서 쿼드트리를 어떻게 적용해볼수 있을까? 문제에서 주어지는 조건을 한 번 생각해보자 

[ 문제 접근 & 알고리즘 ]

1. 0과 1로만 구성된 흑백영상이 모두 0이면 괄호없이 0, 모두 1이면 괄호없이 1을 출력한다.
2. 이때, 흑백영상을 자르는 기준을 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래 4개를 기준으로 해당 영역을 하나의 문자로 압축할 수 있는지 없는지 여부를 판단해야 한다. 
3. 왼쪽 위를 현재 위치로 잡는다면, 나머지 세 영역의 범위는 기준이 되는 현재 위치로 부터 분할한 영역의 크기만큼, x와 y좌표를 이동하면서 잡는다. 
   1. 문제에서 주어진 예제로 간단히 설명하면, 시작위치가 0,0이고 크기가 8인경우
   2. 가장 먼저, 재귀를 시작할 때 모든 값이 0 또는 1로 구성되어 있는지 확인하고 아니라면 크기를 반으로 줄인다. 
   3. 현재위치 0,0을 기준으로 크기의 반(8/2=4)만큼 x와 y값을 이동시킨다. 
   4. 그렇다면 (시작위치x,y,크기)라고 표현했을 때, (0,0,4), (4,0,4), (0,4,4), (4,4,4)이렇게 네 가지의 경우의 수를 구할 수 있는데, 각 경우의 수에서 좌표값을 시작위치로 잡고 2의 검사 과정을 거쳐서 압축할 수 있다면 압축하고, 불가능하다면, 3~4의 과정을 반복하면서 하나의 영역에 대하여 4가지 경우의 수(쿼드 트리)로 분할하여 압축할 수 있는지(정복)를 확인해보면 된다. 
   5. 이때 나누어지는 4가지 경우의 수로 재귀를 호출하면 되는 것이고, 주의할 점은 재귀를 호출하기 전에 괄호를 열고, 재귀가 끝나는 지점에서 괄호를 닫아주면 된다.  

간단한 예를 도식화 하면 아래와 같다. 

[ 소스 코드 ]

package DivideAndConquor;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class _1992_쿼드트리 {
    static int n;
    static int map[][];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        map = new int[n][n];
        
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<n;j++) {
                map[i][j] = str.charAt(j)-'0'; 
            }
        }
        
        dfs(0,0,n);
        System.out.println(sb);
        
    }
    private static void dfs(int x, int y, int size) {
        // TODO Auto-generated method stub
        if(isCompress(x,y,size)) {
            sb.append(map[x][y]);
            return;
        }
        
        int step = size/2;
        
        sb.append('(');
        
        dfs(x,y, step);                                //왼쪽     위 : 현재위치
        dfs(x,y+step, step);                        //오른쪽   위 : 
        dfs(x+step,y, step);                        //왼쪽   아래 : 
        dfs(x+step,y+step, step);                    //오른쪽 아래 : 
        
        sb.append(')');
    }
    
    //압축 가능 여부
    private static boolean isCompress(int x, int y, int size) {
        // TODO Auto-generated method stub
        int val = map[x][y];
        
        //시작값과 비교해서 다르면 불가능 
        for(int i=x; i<x+size; i++) {
            for(int j=y; j<y+size; j++) {
                if(val != map[i][j]) {
                    return false;
                }
            }
        }
        
        //모두 같으면 압축 가능 
        return true;
    }
 
}