색종이 만들기

2630. 색종이 만들기 | 백준

풀이

항상 정방형으로만 자르기 때문에 시작좌표 (r, c)와 사이즈 N을 전달하여 범위 안에 색종이가 색깔에 상관없이 모두 동일한지 확인한다. 만약 범위 안의 색이 동일하지 않으면 N / 2로 범위를 줄여 4분면을 재귀적으로 반복한다.

임의로 1분면 (r, c, half), 2분면 (r, c + half, half), 3분면 (r + (half), c, half), 4분면 (r + (half), c + (half), half) 순서대로 반복하면 다음 그림처럼 진행이 된다.

코드

const path = __dirname + '/input_boj1.txt'
// const path = '/dev/stdin'

const input = require('fs').readFileSync(path).toString().trim().split('\n')
let [N, ...paper] = input

// 첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 
// 둘째 줄에는 파란색 색종이의 개수를 출력

paper = paper.map(el => el.split(' ').map(Number))
let blue = 0
let white = 0

// if 색종이를 만들 수 있으면 count++ 
// else 구역별로 1~4분면을 나누어 검사
// 정방형 모양만 존재하므로 size N / 2를 같이 전달 

const quadrant = (r, c, n) => {
  // 해당 base 좌표부터 N 사이즈까지 같은 색인지 확인 
  if (isFilledSameColor(r, c, n)) {
    // 같은 색이라면 색상이 뭔지 확인 
    if (paper[r][c] === 1) blue++
    else white++
    return 
  } 
  // 다른 색이 섞여 있다면 색종이로 못만듬 -> 다시 사분면으로 확인 
  let half = n / 2
  // 1분면 (좌상)
  quadrant(r, c, half)
  // 2분면 (우상)
  quadrant(r, c + (half), half)
  // 3분면 (좌하)
  quadrant(r + (half), c, half)
  // 4분면 (우하)
  quadrant(r + (half), c + (half), half)
}

const isFilledSameColor = (r, c, n) => {
  const base = paper[r][c] // 분할된 면의 왼쪽 상단 요소 (임의) 
  for (let i = r; i < r + n; i++) {
    for (let j = c; j < c + n; j++) {
      console.log(`${i} ${j}`)
      if (base !== paper[i][j]) return false
    }
  }
  return true
}

quadrant(0, 0, +N)

console.log(`${white}\n${blue}`)