[JavaScript/BOJ] 1018 - 체스판 다시 칠하기

📌 문제(브루트포스 알고리즘)

1018번: 체스판 다시 칠하기

 

📝 풀이

맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우의 정상적으로 칠해진 8 x 8 크기의 체스판을 미리 준비한다.

let white = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']
let black = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']

 

8 x 8 크기의 체스판을 어떻게 떼어야할까❓

row x col 크기의 체스판에서 8 x 8 크기의 체스판을 떼어낼 수 있는 경우의 수를 생각해보자❗❗

(0, 0) 좌표에서 시작하여 (row - 8, col - 8) 좌표까지를 시작으로 8 x 8 크기의 체스판을 떼어낼 수 있다❗❗❗

for (let i = 0; i <= row - 8; i++) {
    for (let j = 0; j <= col - 8; j++) {

      // whiteCheck, blackCheck
      
    }
  }

 

이제 체스판을 떼어낼 수 있는 경우를 차례대로 탐색하면서 정상적으로 칠해진 체스판과 비교를 하면 된다.

맨 왼쪽 위 칸이 흰색, 검은색인 경우를 각각 비교하여 다시 칠해야하는 정사각형의 수를 answer 배열에 추가한다.

마지막으로 Math.min()을 이용하여 answer 배열에서의 최솟값을 리턴하면 된다.

// 전체 코드
const fs = require('fs');
const input = fs.readFileSync('예제.txt').toString().trim().split('\n');

let white = [
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
];

let black = [
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
  'BWBWBWBW',
  'WBWBWBWB',
];

function solution(input) {
  [size, ...arr] = input;
  [row, col] = size.split(' ').map((x) => Number(x));
  arr = arr.map((str) => str.trim('\r').split(''));
  let answer = [];

  // 8 * 8 크기의 체스판을 만드는 경우
  for (let i = 0; i <= row - 8; i++) {
    for (let j = 0; j <= col - 8; j++) {
      // whiteCheck, blackCheck
      let cnt1 = (cnt2 = 0);

      for (let k = 0; k < 8; k++) {
        for (let s = 0; s < 8; s++) {
          if (white[k][s] !== arr[i + k][j + s]) cnt1++;
          if (black[k][s] !== arr[i + k][j + s]) cnt2++;
        }
      }
      answer.push(cnt1);
      answer.push(cnt2);
    }
  }

  return Math.min(...answer);
}

console.log(solution(input));