[BOJ] 1992. 쿼드트리

재귀를 이용한 분할정복 문제였다.

처음에 문제를 보고 이해하는데 오래걸렸다. 이문제는 전체 그림을 4등분하여 같은 숫자를 가진다면 하나의 숫자로 묶는 문제였다. 찾아야하는 범위의 숫자가 계속 반(나누기2) 되는 성질을 보니 재귀를 이용하여 풀수 있을 것 같았다. 그래서 함수 하나를 만들었고, 조건을 만족하지 못한다면 4방향에 대해 범위를 반으로 줄여서 계속 호출해주었다.

이 문제를 풀면서 100%에서 계속 틀렸었는데, 이유는 N=1, N=2인 경우에 문제와 다르게 푼경우가 생겼기에 계속 틀렸다. 항상 예외처리를 할땐 최대와 최소를 의심하는 습관을 들여야겠다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1992_쿼드트리 {
 
    static int N;
    static int[][] map;
    static StringBuilder sb;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        sb=new StringBuilder();
 
        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';    
        }
 
        func(0,0,N);
        System.out.println(sb.toString());
    }
 
    static void func(int i,int j,int n) {
        if(check(i, j, n)==true) {
            sb.append(map[i][j]);
        }else {
            n=n/2;
            sb.append("(");
            func(i,j,n);
            func(i,j+n,n);
            func(i+n,j,n);
            func(i+n,j+n,n);
            sb.append(")");
        }
 
    }
 
    static boolean check(int i,int j,int n) {
        int stanard=map[i][j];
        for(int row=i;row<i+n;row++) {
            for(int col=j;col<j+n;col++) {
                int comp = map[row][col];
                if(comp!=stanard)
                    return false;
            }
        }
        return true;
    }
}