[백준] 1992

쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

풀이

const recurQuadTree = (input, x, y, n) => {
  const firstElem = input[y][x];
  let cnt = 0;
  let stack = [];
  if (n === 1) return firstElem;
  for (let i = y; i < y + n; i++)
    for (let j = x; j < x + n; j++) if (input[i][j] === firstElem) cnt++;
  if (cnt === n * n) return firstElem;
  stack.push(recurQuadTree(input, x, y, n / 2));
  stack.push(recurQuadTree(input, x + n / 2, y, n / 2));
  stack.push(recurQuadTree(input, x, y + n / 2, n / 2));
  stack.push(recurQuadTree(input, x + n / 2, y + n / 2, n / 2));
  return `(${stack.join("")})`;
};

const quadTree = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");
  const n = parseInt(input[0]);
  input.shift();
  input = input.map((n) => n.split("").map(Number));
  console.log(recurQuadTree(input, 0, 0, n));
};

quadTree();

반성회

1. 함수의 정의 : N * N (N은 무조건 2의 제곱수) 크기의 이차원 배열이 모두 같은 글자 (0 또는 1) 로 이루어져 있는지 검사하고, 그렇지 않을 경우 좌표 y, x에서 시작하는 (N / 2) * (N / 2) 크기의 배열 4개로 쪼개 한번 더 검사한 뒤 어떤 글자로 이루어져 있는지 괄호로 감싸 출력
2. 종료조건 : n이 1일 때 검사할 원소가 한 개밖에 없으므로 그대로 반환한다
3. 반환값 :
   1. n이 1일 때, 1 * 1 크기의 배열이 가진 원소를 그대로 출력 (0 또는 1)
   2. n이 1이 아닐 때
      1. (x, y) 지점부터 시작하는 n * n 배열 전체를 검사하여, 첫 번째 원소 (firstElem = input[y][x]) 와 값이 같으면 cnt를 증가시킨다
      2. cnt가 n * n과 같을 경우, n * n 배열 전체가 같은 수로 이루어져 있다는 의미이므로 재귀의 다음 단계로 넘어갈 필요 없이 firstElem을 그대로 반환한다
      3. cnt가 n * n과 같지 않을 경우, 하나라도 다른 수가 있다는 의미이므로 배열을 (n / 2) * (n / 2) 크기의 4개 하위 배열로 쪼개어 하위 배열에서 재귀를 진행한다. 하위 배열의 시작 지점은 각각 (x, y), (x + (n / 2), y), (x, y + (n / 2)), (x + (n / 2), y + (n / 2)) 가 된다
      4. 하위 배열의 결과값을 스택에 임시로 담은 뒤, 문자열로 join하여 괄호로 감싼 값을 반환한다
4. 틀린이유 : 입력값을 받아서 바로 한글자씩 쪼개면 N이 두자리 수 이상일 때 64가 6과 4로 쪼개지는 불상사가 발생하므로 무조건 N을 먼저 받은 뒤 나머지 자리를 쪼개야 한다