[BOJ/1018] 체스판 다시 칠하기 #완전탐색 #체스판

#알고리즘 #백준 #프로그래머스

✅ 문제 설명

✅ 해결 방법

✅ 발생한 문제와 방안

✅ 최종적인 해결 방법

✅ 최적화 방안

그래서 오늘의 TIL(Today I Learned) 학습 키워드

✨ 완전탐색

✨ 체크판

---

✅ 문제

백준 실버4 난이도인 체스판 다시 칠하기 문제로 ✨완전탐색, 전수조사를 통한 최소 연산 구현✨ 방법을 알아보겠습니다.

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

---

✅ 문제 설명

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

가로 × 세로가 N × M인 체스판이 주어진다. 체스판은 흰색(W)과 검은색(B)으로만 이루어져 있다. 이 중 8×8 크기의 보드를 잘라냈을 때, 다시 체스판 규칙에 맞게 칠해야 하는 최소의 칸 수를 구하는 문제다.

---

✅ 해결 방법

• 8×8 구간을 모두 순회하며 탐색
• 각 시작점(i, j)부터 8×8 보드를 자르고,
• “W로 시작하는 체스판”과 “B로 시작하는 체스판”으로 각각 비교
• (i + j) % 2를 이용하면 현재 위치의 색이 어떤 색이어야 하는지 판단 가능
• 각 8×8 영역마다 다시 칠해야 하는 칸 수를 최소화하며 전체 답을 갱신

✅ 발생한 문제와 방안

초기에는 slice를 사용하여 8x8 보드를 잘라서 각각 if문으로 비교하는 방식으로 작성했는데, i, j 짝수/홀수에 따라 분기가 많아 가독성이 떨어졌습니다.

그래서 (i + j) % 2를 이용하여 패턴을 수학적으로 일반화하고, 복잡한 조건문 없이도 시작 색만 바꾸면 비교가 가능한 구조로 리팩토링했습니다.

---

✅ 최종적인 해결 방법

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const solution = () => {
  const [N, M] = input[0].split(" ").map(Number);
  const chess_board = input.slice(1);
  let answer = 64;

  const count_check_board = (startRow, startCol) => {
    let mismatchW = 0;
    let mismatchB = 0;

    for (let i = 0; i < 8; i++) {
      for (let j = 0; j < 8; j++) {
        const expectedW = (i + j) % 2 === 0 ? "W" : "B";
        const expectedB = (i + j) % 2 === 0 ? "B" : "W";

        const actual = chess_board[startRow + i][startCol + j];
        if (actual !== expectedW) mismatchW++;
        if (actual !== expectedB) mismatchB++;
      }
    }

    return Math.min(mismatchW, mismatchB);
  };

  for (let i = 0; i <= N - 8; i++) {
    for (let j = 0; j <= M - 8; j++) {
      const current_count = count_check_board(i, j);
      answer = Math.min(current_count, answer);
    }
  }

  return answer;
};

console.log(solution());

---

✅ 최적화 방안

• slice() 대신 chess_board[startRow + i][startCol + j] 직접 인덱싱으로 메모리 효율 증가
• (i + j) % 2 패턴으로 중복 조건 없이 간결한 구현
• 8×8 블록만 확인하므로 시간 복잡도는 O((N-7)*(M-7) * 64) → 완전탐색으로 충분히 가능

---

✨ 오늘의 TIL(Today I Learned)

• (i + j) % 2를 활용해 체스판 패턴 비교 로직을 간단하게 구현할 수 있다.
• 이와 같은 방식은 격자형 패턴이 반복되는 모든 문제에 일반화할 수 있어 매우 유용하다.
• 완전탐색에서도 패턴화와 인덱스 직접 접근만으로도 코드 품질을 확 높일 수 있다.

--- AI로 작성한 실험적인 글입니다.