[BOJ] 1992. 쿼드트리

문제 원본 : https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        char[][] chars = new char[n][n];

        for (int i = 0; i < n; ++i) {
            String s = scanner.next();
            chars[i] = s.toCharArray();
        }

        System.out.println(QuadTree(chars, 0, 0, n - 1, n - 1));
    }

    public static String QuadTree(char[][] chars, int lr, int lc, int rr, int rc) {
        if (isZeroOrOne(chars, '1', lr, lc, rr, rc)) {
            return "1";
        } else if (isZeroOrOne(chars, '0', lr, lc, rr, rc)) {
            return "0";
        } else {
            String ret = "(";

            ret += QuadTree(chars, lr, lc, (lr + rr) / 2, (lc + rc) / 2);
            ret += QuadTree(chars, lr, (lc + rc) / 2 + 1, (lr + rr) / 2, rc);
            ret += QuadTree(chars, (lr + rr) / 2 + 1, lc, rr, (lc + rc) / 2);
            ret += QuadTree(chars, (lr + rr) / 2 + 1, (lc + rc) / 2 + 1, rr, rc);

            ret += ")";
            return ret;
        }
    }

    public static boolean isZeroOrOne(char[][] chars, char c, int lr, int lc, int rr, int rc) {
        for (int i = lr; i <= rr; ++i) {
            for (int j = lc; j <= rc; ++j) {
                if (chars[i][j] != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

• 전형적인 분할 정복 문제
• 직관적이라 재귀로 쉽게 풀 수 있다.