[백준] 1780 종이의 개수 JavaScript

혅·2024년 7월 17일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

120/215

문제

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

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

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

입력

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

출력

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

예제 입력

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력

10
12
11

내가 했던 풀이 방법

first, second, third는 각각 -1/0/1의 개수를 저장할 변수이다.
0, 0을 시작으로 하고 길이가 N으로 하는 종이부터 순서대로 Div 함수를 통해 확인한다. Div 함수는 종이에서 입력받은 x, y에 위치한 값을 start에 저장하고 해당 위치에서 길이만큼 검사하여 모든 요소가 start와 같은지 검사한다. 만약 다를 경우 isAll을 false로 변경하고 반복문을 탈출한다. 반복문이 끝난 뒤 isAll이 true라면 start 값에 따라 개수를 증가시켜주고, isAll이 false라면 현재 길이를 3배 줄이고 종이를 9등분하여 Div에 재호출한다.
모든 Div가 끝난 뒤 first, second, third에 값을 출력한다.

코드

const fs = require('fs');
let [N, ...paper] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);

for (let i = 0; i < N; i++) {
  paper[i] = paper[i].trim().split(' ').map(Number);
}

let first = 0;
let second = 0;
let third = 0;
function Div(x, y, length) {
  let start = paper[x][y];
  let isAll = true;
  for (let i = x; i < x + length; i++) {
    for (let j = y; j < y + length; j++) {
      if (start !== paper[i][j]) {
        isAll = false;
        break;
      }
    }
    if (!isAll) break;
  }
  if (isAll) {
    if (start === -1) first++;
    else if (start === 0) second++;
    else third++;
  } else {
    let newLength = length / 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        Div(x + i * newLength, y + j * newLength, newLength);
      }
    }
  }
}

Div(0, 0, N);

console.log(first);
console.log(second);
console.log(third);