[백준] 1018. 체스판 다시 칠하기(node.js/javascript/자바스크립트/코딩테스트/브루트포스/완전탐색)

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const height = Number(input[0].split(" ")[0]);
const width = Number(input[0].split(" ")[1]);
const chessboard = [];
let answer = 0;
for (let i = 1; i <= height; i++) {
  input[i] = input[i].slice(0, width);
  chessboard.push(input[i].split(""));
}

const whiteFirstPaint = (i, j) => {
  let count = 0;
  for (let w = i; w <= i + 7; w++) {
    for (let h = j; h <= j + 7; h++) {
      if ((w % 2 === 0 && h % 2 === 1) || (w % 2 === 1 && h % 2 === 0)) {
        // B인지 검사
        count = chessboard[h][w] === "B" ? count : count + 1;
      } else if ((w % 2 === 0 && h % 2 === 0) || (w % 2 === 1 && h % 2 === 1)) {
        // W인지 검사
        count = chessboard[h][w] === "W" ? count : count + 1;
      }
    }
  }
  return count;
};

const blackFirstPaint = (i, j) => {
  let count = 0;
  for (let w = i; w <= i + 7; w++) {
    for (let h = j; h <= j + 7; h++) {
      if ((w % 2 === 0 && h % 2 === 1) || (w % 2 === 1 && h % 2 === 0)) {
        // W인지 검사
        count = chessboard[h][w] === "W" ? count : count + 1;
      } else if ((w % 2 === 0 && h % 2 === 0) || (w % 2 === 1 && h % 2 === 1)) {
        // B인지 검사
        count = chessboard[h][w] === "B" ? count : count + 1;
      }
    }
  }
  return count;
};

for (let i = 0; i + 7 < width; i++) {
  for (let j = 0; j + 7 < height; j++) {
    const whiteFirst = whiteFirstPaint(i, j);
    const blackFirst = blackFirstPaint(i, j);
    if (i === 0 && j === 0) {
      answer = Math.min(whiteFirst, blackFirst);
    } else {
      if (Math.min(whiteFirst, blackFirst) < answer) {
        answer = Math.min(whiteFirst, blackFirst);
      }
    }
  }
}
console.log(answer);

 

이 문제를 풀기 위한 아이디어

일단 이 문제는 브루트포스(완전탐색) 이므로 가능한 경우의 수를 모두 따져준 후 최소값을 구하면 된다.

체스판은 위에 그림처럼 흰색이 먼저 칠해지느냐, 검은색이 먼저 칠해지느냐 이 2가지 경우가 있고,

주어진 판에서 8x8로 자르며 자른 판을 흰색이 먼저 칠해진 판 혹은 검정색이 칠해진 판과 비교하여 다른 부분만 count하여 둘 중 어느 것이 더 최소값인지 구하면 된다.

 

이 때 주어진 판은 8x8로 자르는 방법은 다음과 같다.

이런 식인 것이다. 그러므로 처음에 판을 자르기 위해 반복문을 돈다.

i는 0부터 시작하고 i에 7을 더한 값이 가로 길이보다 작을때까지 돌고

j는 0부터 시작하여 j에 7을 더한 값이 세로 길이보다 작을때까지 돈다.

 

이 때 i가 0이라면 0~7 (가로)을 범위로 사각형이 움직인다고 생각하면 된다.

마찬가지로 j가 0이라면 0~7(세로)를 범위로 사각형이 움직인다.

 

그리고 whiteFirst와 blackFirst 함수를 실행하여 비교한 후 다르면 칠해야하는 부분이므로 count를 증가시킨다.

이 때 whiteFirst 판의 경우 가로가 짝수, 세로가 짝수이면 W / 가로가 홀수, 세로가 홀수이면 W / 가로가 짝수, 세로가 홀수 이면 B / 가로가 홀수, 세로가 짝수이면 B이어야 한다. 

blackFirst 판의 경우는 whiteFirst 판과 반대이다.

 

이렇게 하여 반복문을 계속 돌며 최솟값이 나오면 업데이트 한 후 이를 마지막에 출력해주면 된다.