[백준_1018] 체스판 다시 칠하기 (완전탐색 - 자바스크립트)

문제

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

1018번: 체스판 다시 칠하기

How to solve?

 

[1] Brute Force

 

8*8 크기의 체스판에서 수정을 가장 적게 하는 경우를 찾으면 되는 문제이다.

 

그런데 체스판을 만들 수 있는 경우가 아래의 2가지로 나뉘게 된다.

1) 체스판의 시작이 흰색 일 때 ( WBWBWBWB )


2) 체스판의 시작이 검은색 일 때  ( BWBWBWBW )

고로 주어진 전체 바둑판의 행과 열의 길이가 각각 8을 넘는다면, 8씩 잘라가면서 1) 흰색일 때, 수정이 필요한 개수 / 2) 검은색 일 때, 수정이 필요한 개수를 구해서 최소 값과 비교하며 정답을 구해 주면 된다.

 

function solution(board) {
  let minimum = 64;

  for (let i = 0; i <= N - 8; i++) {
    for (let j = 0; j <= M - 8; j++) {
      let typeB = 0; // 검은색으로 시작
      let typeW = 0; // 흰색으로 시작
      for (let k = i; k < i + 8; k++) {
        for (let l = j; l < j + 8; l++) {
          if ((k + l) % 2 === 0) { // (0,0), (0,2), (1,1)
            if (board[k][l] === "W") { 
              typeB++; // B 자리에 W가 있는 경우 => 수정 필요 => +
            } else {
              typeW++;
            }
          } else { // (0,1), (0,3), (1,0)
            if (board[k][l] === "B") {
              typeB++; //W 자리에 B가 있는 경우 => 수정 필요 => +
            } else {
              typeW++;
            }
          }
        }
      }
      if (minimum > typeB) minimum = typeB;
      if (minimum > typeW) minimum = typeW;
    }
  }
  console.log(minimum);
}

let [N, M] = [10, 13];

let board = [
  ["B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B", "W"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B", "W"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B", "W"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B", "W"],
  ["B", "B", "B", "B", "B", "B", "B", "B", "B", "W", "B", "W", "B"],
  ["W", "W", "W", "W", "W", "W", "W", "W", "W", "W", "B", "W", "B"],
  ["W", "W", "W", "W", "W", "W", "W", "W", "W", "W", "B", "W", "B"],
];

solution(board);