[백준, 자바, 1992번] 쿼드트리

풀이

• 해당 문제는 처음에 뭔가 했는데
• 단순히 전체를 체크한 뒤 0과 1이 섞여 있다면
• 사분면으로 나누는 분할과 확인을 거치는 정복에 관련한 문제
• 다만 사분면의 범위를 지정하는데 잠시 이슈가 있었던게
• 짝수로만 범위가 주어질때는 예를 들어
• si=0,ei=8,sj=0,ej=8,ln=8 이라고 할 때
• 사분면을 나눌 때 그냥 절반으로 해서
• ei를 ei/2 이런식으로 하니까 길이가 1인 경우를 체크할 땐
• 원하는 배열 탐색이 안되었다.
• 그래서 수정한 건 시작과 끝을 더한 뒤 2를 나눈 값으로 지정하여 아래와 같이 작성 후 해결.

 

import java.io.*;
import java.util.StringTokenizer;

public class _1992 {
    static int N;
    static String[][] mtx;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        mtx = new String[N][N];
        for (int i=0; i<N; i++) {
            String row = br.readLine();
            for (int j=0; j<N; j++) mtx[i][j]=String.valueOf(row.charAt(j));
        }
        find(0,N,0,N,N);
        System.out.println(sb);
    }

    public static void find(int si, int ei, int sj, int ej, int ln) {
        String now = mtx[si][sj];
        boolean state = true;
        if (ln!=1) {
            for (int i=si; i<ei; i++) {
                for (int j=sj; j<ej; j++) {
                    if (!mtx[i][j].equals(now)) {
                        state = false;
                        break;
                    }
                }
                if (!state) break;
            }
        }
        if (state) sb.append(now.equals("0")?"0":"1");
        else {
            int n_ln = ln/2;
            sb.append("(");
            find(si, (si+ei)/2, sj, (sj+ej)/2, n_ln); // 1사분면

            find(si, (si+ei)/2, (sj+ej)/2, ej, n_ln); // 2사분면

            find((si+ei)/2, ei, sj, (sj+ej)/2, n_ln); // 3사분면

            find((si+ei)/2, ei, (sj+ej)/2, ej, n_ln); // 4사분면
            sb.append(")");
        }
    }
}