백준 1018 : 체스판 다시 칠하기

💡기본 정보

유형
: 브루트포스
풀이 날짜
: 2025년 01월 10일 
풀이방법 한줄 요약
: 정답인 체스판과 맞는지 확인 후 다시 칠해야 하는 부분을 체크함

 

💡문제에서 구해야 할 것

MN개 단위 정사각형으로 나눠져 있는 M*N크기의 보드를 잘라서 8*8 크기의 체스판을 만들려고 함 
체스판을 색칠하는 경우가 맨 위쪽 위 칸이 흰색 / 검은색 인 경우만 존재
보드가 체스판처럼 칠해져있다는 보장이 없으니 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠함
지민이가 다시 칠해야하는 정사각형의 최소 개수를 구함

 

- 입력 : 첫 줄에 N과 M이 주어짐 N과 M은 8보다 크거나 같고 , 50보다 작거나 같은 자연수 
             둘째 줄 부터 N개의 줄에는 보드의 각 행의 상태가 주어짐 B : 검은색 W : 흰색
  출력 : 첫째 줄에 지민이가 다시 칠해야하는 정사각형 개수의 최솟값 출력

 

💡알고리즘 설계
- 8*8이 가능한 경우의 수 두 개 정의 
흰색이 먼저 온 경우
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

검은색이 먼저 온 경우
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
- 흰색이 온 경우나 검은색이 온 경우를 계산해서 흰색이 앞에 오는게 최솟값인지 검은색이 앞에 오는게 최솟값인지 확인

- 최종적인 최솟값을 구해서 출력함

 

💡CODE

const fs = require("fs");
const list = fs.readFileSync(0, "utf8").toString().trim().split("\n");

const NM = list.shift().split(" ");
const N = Number(NM[0]);
const M = Number(NM[1]);

const blackChess = [
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
];

const whiteChess = [
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
];

const board = list.map((line) => line.split(""));

function check(x, y) {
  let checkWhite = 0;
  let checkBlack = 0;
  for (let i = y; i < y + 8; i++) {
    for (let j = x; j < x + 8; j++) {
      if (board[i][j] !== whiteChess[i - y][j - x]) {
        checkWhite++;
      }
      if (board[i][j] !== blackChess[i - y][j - x]) {
        checkBlack++;
      }
    }
  }
  return Math.min(checkWhite, checkBlack);
}

function Chess() {
  let min = Infinity;
  for (let i = 0; i <= N - 8; i++) {
    for (let j = 0; j <= M - 8; j++) {
      const result = check(j, i);
      if (result < min) {
        min = result;
      }
    }
  }
  return min;
}

console.log(Chess());

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

       범위 계산을 잘못해서 틀림
       N-8이나 M-8이 범위인 이유
          : i+7 <= N-1 , i<=N-8

          : j+7 <= M-1 , j<=M-8 

💡 다른 풀이 or 기억할정보

board[i][j] !== whiteChess[i-y][j-x]{checkWhite++;}

: 입력한 체스판에 현재 문자와 정답 체스판의 대응되는 문자를 비교함