[백준] 1780

종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

풀이

const recurPaper = (input, n, x, y, stack) => {
  const cur = input[y][x];
  if (n === 1) {
    stack[cur + 1]++;
    return;
  }
  let cnt = 0;
  for (let i = y; i < y + n; i++)
    for (let j = x; j < x + n; j++) if (input[i][j] === cur) cnt++;
  if (cnt === n * n) stack[cur + 1]++;
  else {
    for (let i = 0; i < 3; i++)
      for (let j = 0; j < 3; j++)
        recurPaper(input, n / 3, x + (j * n) / 3, y + (i * n) / 3, stack);
  }
};

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

paper();

반성회

1. 함수의 정의
   • 한 배열 조각 (n * n 크기) 안의 모든 수가 같다면 인자로 들어온 stack 배열의 값을 조정한다
     • -1일 경우 stack[0]++
     • 0일 경우 stack[1]++
     • 1일 경우 stack[2]
   • 어느 한 수라도 같지 않다면 n * n 크기의 배열을 9등분하고, (y, x) 좌표에서 시작하는 (n / 3) * (n / 3) 크기의 배열에 대해 같은 과정을 반복한다
   • stack 배열은 같은 수로 이루어진 종이의 개수를 나타낸다
2. 종료조건 : n이 1일 때 (n은 3의 k승으로, 3으로 나누다 보면 언젠가 반드시 1에 도달)
3. 반환값 : 없음 (인자로 들어온 stack 배열의 값을 증가)

---

1. cur은 현재 종이 조각에서 가장 첫 번째의 수를 나타냄 (-1 or 0 or 1)

2. n이 1일 때는 현재 조각이 1 * 1 크기이므로 (더이상 9등분할 수 없음) 현재 값에 대한 개수를 증가

3. 그 외의 경우, [y, x] 부터 [y + n, x + n] 까지 모든 칸이 같은 수로 이루어져 있는지 검사

   1. 같은 수로 이루어져 있을 경우, 재귀를 들어가지 않고 stack의 특정 인덱스 값을 증가시키고 함수 종료

   2. 같은 수로 이루어져 있지 않은 경우, 9등분하여 각각의 조각에 대해 재귀

       recurPaper(input, n / 3, x + (j * n) / 3, y + (i * n) / 3, stack);

   3. 각 조각은 (n / 3) * (n / 3) 크기가 된다