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

[Silver 4]1018 체스판 다시 칠하기

문제 링크

구분

알고리즘 > 완전탐색

풀이 요약

8*8 체스판에서 흰색 또는 검은색으로 시작하는 체스판 패턴과 비교하여 최소한으로 체스판을 다시 칠하는 경우의 수를 구하는 문제

나의 풀이

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

let [board, ...arr] = input;
const [n, m] = board.split(" ");
arr = arr.map((i) => i.split(""));
let answer = [];

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

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

function WhiteBoard(x, y) {
  let count = 0;
  for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
      if (arr[i + x][j + y] !== whiteboard[i][j]) {
        count++;
      }
    }
  }
  return count;
}

function BlackBoard(x, y) {
  let count = 0;
  for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
      if (arr[i + x][j + y] !== blackboard[i][j]) {
        count++;
      }
    }
  }
  return count;
}

for (let i = 0; i < n - 7; i++) {
  for (let j = 0; j < m - 7; j++) {
    answer.push(WhiteBoard(i, j));
    answer.push(BlackBoard(i, j));
  }
}
console.log(Math.min(...answer));

문제에서는 88 체스판에 대해 설명하면서 체스판의 크기가 88을 넘어갈 때는 체스판을 잘라서 색을 덧칠한다고 했습니다.

예를 들어, 입력값으로 10 13으로 n과 m이 주어진 경우 , 1013의 부분을 88로 잘라서 잘라낸 부분을 모두 탐색합니다. ( 이 문제가 완전탐색 문제인 이유이기도 합니다. 모든 부분을 탐색해야 하기 때문에)

잘라낸 부분이 whiteboard, blackboard와 얼마나 일치하는지를 확인하게 되는데 만약 일치하지 않는 부분이 있다면 count를 증가시키고 이를 반환합니다.

 

WhiteBoard와 BlackBoard 함수는 잘라낸 8*8 영역을 변경할 필요가 있는 칸의 개수를 셉니다.

또, 체스판의 모든 8*8 부분을 검사하기 위해서 시작 가능한 좌표의 범위를 제한하기 위해서 for문의 범위를 n-7, m-7로 설정해 주었습니다.

만약 (i, j)가 너무 끝에 가깝게 되면 8*8 영역을 만들 수 없기 때문입니다.

예를 들어, 체스판의 크기가 10*13이라고 했을 때 체스판의 행 수가 10이기 때문에 i(행의 시작 인덱스)는 10-7=3 까지만 가능합니다. 따라서 i는 0부터 2까지만 가능해집니다.

또 열 기준으로 가능한 시작 지점은 체스판의 열 수가 13이기 때문에 j(열의 시작 인덱스)가 13을 넘겨서 8열을 포함할 수 없게 됩니다. 따라서 j는 0,1,2,3,4,5의 값까지만 가질 수 있게 됩니다.

 

이렇게 되면 10*13에서 체스판 탐색 시작 좌표는 아래와 같습니다.

(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)

(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)

(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)

이 좌표들에서 8*8 영역을 검사해서 주어진 체스판과 일치하도록 색을 변경해야 할 횟수를 계산하게 됩니다.

배운 점

1. for문의 범위를 세우는 것이 어려웠는데, 영역을 탐색할 때 유효 범위를 설정하는 것을 배우고 적용할 수 있었습니다.
2. 그리고 체스판과 같은 2차원 배열에서 특정 부분을 잘라서 비교하는 방법을 새로 알게 되었는데 이는 count변수를 활용해서 몇 개가 다른지 비교할 수 있었습니다.