문제 링크

문제 간단 해석

공간을 쪼개가며 내부 값을 확인. 잘 쪼개기만 하면 쉬운 문제.

Java

풀이 코드

class Solution {
    private int[] answer = new int[2];
    private int[][] arr;

    public void check(int r1, int c1, int r2, int c2) {
        int val = arr[r1][c1];

        for (int r = r1; r < r2; r++) {
            for (int c = c1; c < c2; c++) {
                if (arr[r][c] != val) {
                    check(r1, c1, (r1 + r2) / 2, (c1 + c2) / 2);
                    check(r1, (c1 + c2) / 2, (r1 + r2) / 2, c2);
                    check((r1 + r2) / 2, c1, r2, (c1 + c2) / 2);
                    check((r1 + r2) / 2, (c1 + c2) / 2, r2, c2);
                    return;
                }
            }
        }

        answer[val]++;
    }

    public int[] solution(int[][] arr) {
        this.arr = arr;

        check(0, 0, arr.length, arr[0].length);

        return answer;
    }
}

해석

int val = arr[r1][c1];

for (int r = r1; r < r2; r++) {
    for (int c = c1; c < c2; c++) {
        if (arr[r][c] != val) {
            check(r1, c1, (r1 + r2) / 2, (c1 + c2) / 2);
            check(r1, (c1 + c2) / 2, (r1 + r2) / 2, c2);
            check((r1 + r2) / 2, c1, r2, (c1 + c2) / 2);
            check((r1 + r2) / 2, (c1 + c2) / 2, r2, c2);
            return;
        }
    }
}

answer[val]++;

맨 좌측 상단 값을 기준으로 잡는다.
이중 for문을 돌려가며 내부 값을 확인하다가, 기준값과 다르다면 공간을 4부분으로 쪼개서 재귀를 돌린다.

내부 값이 다 같다면 answer의 0 혹은 1 값을 증가.

Python

풀이 코드

def solution(arr):
    answer = [0, 0]
    stack = [(0, 0, len(arr))]

    def check(y, x, n):
        now = arr[y][x]
        for i in range(n):
            for j in range(n):
                if arr[y + i][x + j] != now:
                    half = n // 2
                    stack.append((y, x, half))
                    stack.append((y + half, x, half))
                    stack.append((y, x + half, half))
                    stack.append((y + half, x + half, half))
                    return

        answer[now] += 1

    while stack:
        check(*stack.pop())

    return answer

해석

def check(y, x, n):
    now = arr[y][x]
    for i in range(n):
        for j in range(n):
            if arr[y + i][x + j] != now:
                half = n // 2
                stack.append((y, x, half))
                stack.append((y + half, x, half))
                stack.append((y, x + half, half))
                stack.append((y + half, x + half, half))
                return

    answer[now] += 1

어차피 n * n 값을 확인하는건 같으니, 해당 크기만큼 값을 확인하되 시작점을 잘 선택하여 돌리게끔 한다.