[240528] 알고리즘 리부트 61일차 - 백준 2630 자바

처음 상태에서 모두 동일한 색인지를 확인한 후 그렇지 않다면 1~4사분면으로 시작점을 달리하여 재귀를 진행하도록 구현했다. 해당 범위 내에서 첫 수를 저장하고 달라진다면 다시 길이를 반으로 줄이고 다시 재귀를 돌도록 진행해서 같은 수로 작성된 정사각형인 경우에만 정답 배열에 더해주었다. 처음에는 1~4사분면 순회를 각각 작성했는데 가만히 보니 그냥 재귀의 시작점인 행렬 값을 바꿔주면 되는 것이라서 간단히 작성할 수 있었다. 재귀에 더더더 익숙해지면 좋겠다! 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int n;
    private static int[][] paper;
    private static int[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        paper = new int[n][n];

        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                paper[i][j] = Integer.parseInt(st.nextToken());
        }

        answer = new int[2];

        int first = paper[0][0];

        boolean same = true;

        outer:
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (first != paper[i][j]) {
                    same = false;
                    check(0, 0, n / 2);
                    check(0, n / 2, n / 2);
                    check(n / 2, n / 2, n / 2);
                    check(n / 2, 0, n / 2);
                    break outer;
                }
            }

        if (same) answer[first]++;


        System.out.print(answer[0] + "\n" + answer[1]);


    }

    private static void check(int r, int c, int len) {

        int first;
        boolean same;

        // 기저 조건
        if (len == 0) return;
        
        // 재귀 조건
        first = paper[r][c];
        same = true;
        outer:
        for (int i = r; i < r + len; i++)
            for (int j = c; j < c + len; j++) {
                if (first != paper[i][j]) {
                    same = false;
                    check(r, c, len / 2);
                    check(r, c + len / 2, len / 2);
                    check(r + len / 2, c + len / 2, len / 2);
                    check(r + len / 2, c, len / 2);
                    break outer;
                }
            }
        if (same) answer[first]++;
    }
}