[백준/JavaScript] 프렉탈 평면(1030)

문제

https://www.acmicpc.net/problem/1030

 

프렉탈 평면은 다음과 같이 커진다. 시간 0에서 프렉탈은 흰색 정사각형 하나이다. 단위 시간(1)이 진행될 때마다 N×N개의 크기가 동일한 단위 정사각형으로 나누어진다. 만약 나누어진 정사각형이 흰색이라면 가운데 K×K 정사각형이 검정색으로 채워진다. N과 K는 둘 다 홀수이거나, 둘 다 짝수이다.

예를 들어, N=3, K=1이라면, 시간 1에 3×3 정사각형이 된다. 가운데 정사각형은 검정색이고, 나머지는 흰색이 된다. 시간 2때 9×9 정사각형이 되고, 17개는 검정이고, 나머지는 흰색이다.

 

 

s, N, K, R1, R2, C1, C2가 주어질 때, 시간 s일 때, R1행 C1열부터 R2행 C2열까지의 모습을 출력하는 프로그램을 작성하시오.

---

풀이

• 분할정복 문제

// 백준 - 프렉탈 평면(1030)
let s, N, K, R1, R2, C1, C2;
let answer;
const solution = ( input ) => {
  [ s, N, K, R1, R2, C1, C2 ] = input.shift().split(' ').map((o) => parseInt(o));
  answer = new Array(51).fill(0);
  for(let i = 0; i < 51; i++) {
    answer[i] = new Array(51).fill(0);
  }
  
  fractal(0, 0, Math.pow(N, s), false);

  for(let i = 0; i <= R2 - R1; i++) {
    let printLine = ""
    for(let j = 0; j <= C2 - C1; j++) {
      printLine += answer[i][j].toString();
    }
    console.log(printLine);
  }
}

const fractal = ( x, y, size, isBlack ) => {
  if(x > C2 || x + size <= C1 || y > R2 || y + size <= R1) return; // 범위 벗어나면 패스

  // 분할 끝
  if(size == 1) {
    answer[y - R1][x - C1] = isBlack ? 1 : 0;
    return;
  }

  let nextSize = size / N;
  let black = [(N - K) / 2, N - (N - K) / 2];
  for(let i = 0; i < N; i++) {
    let nextY = y + nextSize * i;
    for(let j = 0; j < N; j++) {
      let nextX = x + nextSize * j;
      fractal(nextX, nextY, nextSize, isBlack || (i >= black[0] && i < black[1])&& (j >= black[0] && j < black[1]));
    }
  }
}

/*
테스트용: __dirname + '/input.txt'
제출용: '/dev/stdin'
*/
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

solution(input);