[자바/분할정복] 백준 1992. 쿼드트리

문제

문제 링크

해석

이 문제는 대표적인 분할정복 문제다. 분할정복은 재귀를 이용하여 큰 문제를 작은 문제로 나눠서 해결하는 알고리즘이라고 한다. 이번에 학습하면서 연습문제 삼아 풀어봤다. 이것과 더불어 Z라는 문제도 유명하다.

나는 누적합을 같이 적용하여 풀었고, 기준에 미치지 못하면 재귀를 타고 들어가서 처리할 수 있도록 분할정복 로직을 구성하였다.

코드

public class BOJ_1992_쿼드트리 {
    /*
    * 실행시간 : 264 ms
    *
    * 메모리 : 17020 KB
    * */
    static int[][] ps;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        ps = new int[n+1][n+1];

        /* 배열 초기화 */
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(s.substring(j,j+1));
            }
        }

        /* 누적합 구하기 */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                ps[i][j] = arr[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
            }
        }

        go(0, 0, n);
    }

    private static void go(int r, int c, int n) {
        int res = ps[n+r][n+c] - ps[n+r][c] - ps[r][n+c] + ps[r][c];
        if (res == n * n) {
            System.out.print(1);
            return;
        } else if (res == 0) {
            System.out.print(0);
            return;
        } else {
            System.out.print("(");
            n = n / 2;
            go(r, c, n);
            go(r, c + n, n);
            go(r + n, c, n);
            go(r + n, c + n, n);
            System.out.print(")");
        }
        return;
    }
}