[Javascript] 백준 1018. 체스판 다시 칠하기

1. 입력으로 주어진 nxm 보드판에서 체스판(8x8)로 자른다.

2. 체스판(8x8) 에서 예상한 컬러와 현재 컬러가 다르다면 변경 횟수를 1증가시킨다.

 

체스판의 종류는 2가지

1. (0,0) 이 블랙(B)으로 시작하면서 교차로 색이 나오는 체스판 

2. (0,0) 이 화이트(W)로 시작하며서 교차로 색이 나오는 체스판

 

두 개의 경우는 다 비교해야 하지만, 

사실은 둘 중 하나만 하더라도 64 - (둘 중 하나를 돌렸을 때 나오는 경우) 로 나머지도 구할 수 있었다.

편의상 1, 2 체스판을 각각 블랙 체스판, 화이트 체스판이라고 말하겠다.

 

따라서 나는 화이트 체스판이라고 가정해서 풀었다.

화이트 체스판에서 예상한 컬러 구하는 법

1. 인덱스가 홀수 + 홀수 이거나 짝수 + 짝수 -> 화이트(W)

2. 인덱스가 홀수 + 짝수 이거나 짝수 + 홀수 -> 블랙(B)

 

👉 인덱스를 모두 더했을 때 홀수의 경우 블랙(B)이고, 짝수일 경우 화이트(W) 알 수 있다.

 

전체 코드는 다음과 같다.

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

const [n, m] = input[0].split(" ").map(Number);
const board = input.slice(1);

let color, expectedColor;
let answer = Infinity;

for (let i = 0; i <= n - 8; i++) {
  for (let j = 0; j <= m - 8; j++) {
    let whiteChessCase = 0; // 화이트 체스(화이트로 시작하는 체스판)에서의 틀린 색의 개수

    for (let r = 0; r < 8; r++) {
      for (let c = 0; c < 8; c++) {
        color = board[r + i][c + j];
        expectedColor = (r + i + c + j) % 2 ? "B" : "W";

        if (color !== expectedColor) {
          whiteChessCase++;
        }
      }
    }
    // 최소 변경 횟수 업데이트 (화이트 체스일 때 변경해야 하는 수, 블랙 체스일 때 변경해야 하는 수, answer)
    answer = Math.min(whiteChessCase, 64 - whiteChessCase, answer);
  }
}

console.log(answer);

 

문제

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