문제

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

nXn 크기가 1이상 1024인 정사각형 배열이 입력된다.
n은 2의 거듭제곱이며 숫자는 모두 0 혹은 1이 입력된다.
이를 쿼드압축후 0과 1의 개수를 구하라.

당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

풀이방법

문제를 딱 보자마자 직관적으로 분할정복으로 풀면 되겠다고 생각했다.
방법은 간단한데 아래와 같다.

1. 시작좌표 ~ 끝좌표가 모두 같은 숫자라면 정답에 1을 더해준다.
2. 아니라면 현재 위치에서 시작좌표를 4개로 쪼개서 다시 탐색하고
3. 시작좌표 ~ 끝좌표가 모두 같은숫자일때까지 1,2를 반복한다.

이렇다.

코드

const solution = board => {
  const result = [0, 0];
  const isEverySameNumber = (sy, sx, ey, ex, first) => {
    for (let i = sy; i < ey; i++) {
      for (let j = sx; j < ex; j++) {
        if (first !== board[i][j]) return false;
      }
    }
    return true;
  };

  const dfs = (sy, sx, size) => {
    const first = board[sy][sx];
    if (isEverySameNumber(sy, sx, sy + size, sx + size, first)) {
      result[first]++;
      return;
    }

    const newSize = size / 2;
    dfs(sy, sx, newSize);
    dfs(sy + newSize, sx, newSize);
    dfs(sy, sx + newSize, newSize);
    dfs(sy + newSize, sx + newSize, newSize);
  };

  dfs(0, 0, board.length);
  return result;
};