🔎 쿼드압축 후 개수 세기

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/68936

📄 제출 코드

function solution(arr) {
  checking(arr, 0, 0, arr.length);
  return answer;
}
let answer = [0,0]
function checking(arr, x, y, n) {
  let flag = true;
  if (n == 1) return answer[arr[x][y]]++;
  for (let i = x; i < x + n; i++) {
    for (let j = y; j < y + n; j++) {
      if (arr[x][y] != arr[i][j]) {
        flag = false;
        break;
      }
    }
  }
  if (flag) return answer[arr[x][y]]++;
  n /= 2;
  checking(arr, x, y, n);
  checking(arr, x+n, y, n);
  checking(arr, x, y+n, n);
  checking(arr, x+n, y+n, n);
}
let arr = [[1, 1, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [1, 1, 1, 1]];
console.log(solution(arr));

처음엔 작은 사각형부터 점점 키워나가는 방향을 생각을 했는데 못 풀었다.
그래서 다른 사람의 코드를 참고했는데 보고도 이해하는데 오래걸린 문제다.
풀이는 다음과 같다.
가장 큰 사각형부터 줄여나가면서 확인을 하는데

0	1

2	3

이렇게 4개 분면을 생각해서 checking메소드를 4번 재귀한다.
시작점과 길이는 가장 큰 사각형부터 시작해서 만약 시작점과 반복하면서 도는게 다르면 flag는 false로 하고, n을 반으로 쪼갠다.
그리고 4개의 다른 시작점으로 나눈거의 4분면을 탐색한다.
문제에서 arr은 0아니면 1이라고 나와있고, 정답은 [0의수, 1의수]를 출력한다.
flag가 반복을 다돌아도 계속 true면 시작점의 위치값의 수를 1증가시키고, 변의길이가 1이면 해당값의 수를 1증가시켜서 answer을 구한다.

📘 참고

https://youngslog.medium.com/알고리즘-쿼드압축-후-개수-세기-javascript-abf959607d3b