[백준 1992] - [분할정복] - 쿼드트리

문제 링크 : https://www.acmicpc.net/problem/1992

---

이 문제는 백준 1780번 종이의 개수 문제와 같은 형식으로 푸는 문제이다. 

1780 문제를 풀어봤으면 이문제는 쉽게 풀릴거고 또 이 문제를 풀면 1780 문제도 쉽게 풀릴것이다. 

1780 문제 링크와 본인의 풀이 소스 링크도 첨부하겠다. 

---

백준 1780번 종이의 개수

2018/11/28 - [알고리즘/분할정복(Divide and conquer)] - [백준 1780]-[분할정복]-종이의 개수 (JAVA)

---

이 문제를 접근하기전 사이즈의 입력 크기 N 부터 확인해야한다. 

아무 수나 입력이 되는것이 아니라 2의 배수로 입력이 된다고 한다. 

즉 N * N 의 쿼리가 전분 같은 수로 돼 있지 않으면 N/2 * N/2  * 4 만큼 다시 조회를 하면 된다. 

행과 열의 사이즈를 절반을 줄이면 크기가 1/4이 되고 4개의 정사각형이 만들어지고 이 4개의 정사각형을 탐색하면된다.

전혀 어렵지 않으니 한번 소스를 보면서 이해하길 바란다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int size;
    public static int[][] quadTree;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        size = Integer.parseInt(br.readLine());
        quadTree = new int[size][size];
        sb = new StringBuilder();
        
        for(int i=0; i < size; i++) {
            String str = br.readLine();
            for(int j=0; j < size; j++) {
                quadTree[i][j] = Integer.parseInt(str.substring(j, j+1));
            }
        }
        
        srcQuadTree(0, 0, size);
        System.out.println(sb.toString());
    }
    
    public static boolean isAble(int row, int col, int size) {
        int t = quadTree[row][col];
        
        for(int i=row; i < row+size; i++) {
            for(int j=col; j < col+size; j++) {
                if(t != quadTree[i][j]) return false;
            }
        }
        return true;
    }
    
    public static void srcQuadTree(int row, int col, int size) {
        if(isAble(row, col, size)) {
            sb.append(quadTree[row][col]);
        }else {
            sb.append("(");
            int newSize = size/2;
            
            srcQuadTree(row, col, newSize);
            srcQuadTree(row, col + newSize, newSize);
            srcQuadTree(row + newSize, col, newSize);
            srcQuadTree(row + newSize, col + newSize, newSize);
            
            sb.append(")");
        }
    }
}