[완전탐색(BruteForce)] 백준 1018 체스판 칠하기 ( by node js )

1. 문제

2. 문제 접근법

문제를 풀 때 놓치지 말아야 할 포인트는 크게 2가지라고 생각이 든다.

 

2-1) 주어진 크기를 -> 8 * 8 로 자른다.

 

8*8 로 자르는 것은 크게 어렵지 않다.

주어진 N, M 에서 각각 -8을 뺀 이후에 for loop를 돌려 주면 된다.

 

 

2-2) 가장 최소한의 오류가 있는 "체스판" 을 선정한다.

 

이 문제의 쟁점은 가장 오류가 적은 체스판을 선정 하는 것이다.

 

이 때, 오류가 적다는 것은 

 

White로 체스판이 시작이 됬다면 다음과 같은 규칙을 따르는 것이고,

 

WBWBWBWB 

BWBWBWBW

 

BLACK으로 체스판이 시작이 됬다면 다음과 같은 규칙을 따르는 것이다.

 

BWBWBWBW
WBWBWBWB 

 

즉,  위의 정보를 통해 유추 해낼 수 있는 것이 하나 더 있는데 그것은 바로!  최소한의 오류를 가진 판을 확인 하기 위해서 우리가 어떤 색을 기점으로 시작했는지 아는 것이 중요하다.

 

필자의 경우, 이를 조건문으로 나누어 구현 했는데 하단의 코드를 보며 추가적으로 설명하며 이 글을 마치도록 하겠다 !

 

3. 코드

 

let fs = require("fs");
let inputData = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split(/\r\n|\r|\n/);

let N = parseInt(inputData[0].split(" ")[0]);
let M = parseInt(inputData[0].split(" ")[1]);
let board = [];

for (let i = 1; i <= N; i++) {
  board.push(inputData[i].split(""));
}

let minimum = 64;

// 8씩 감소 시키는 이유는, 8*8 짜리 1판만 필요 하기 때문에
// 여분을 미리 제거 해두는 것이다.
for (let i = 0; i <= N - 8; i++) {
  for (let j = 0; j <= M - 8; j++) {
    let typeA = 0; // 왼쪽 상단이 white로 시작하는 것
    let typeB = 0; // 왼쪽 상단이 black으로 시작하는 것
    
    // i,j는 8*8 만큼의 크기를 제외한 변수이기에 i ~ i+8 까지는 8*8 체스판을 이동시킬 수 있고
    // 이를 통해 가장 적은 오류를 가진 체스판츨 찾을 수 있다.
    
    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) 등 짝수 자리가
		  //  white 라면, 좌측 상단이 백색으로 시작하는 것이고
          if (board[k][l] === "W") {
            typeA++;
          // (0,1) (0,3) (1,0) 등 홀수 자리가
		  //  white 라면, 좌측 상단이 흑색으로 시작하는 것이다.
          } else {
            typeB++;
          }
          
        } else {
          // (0,1) (0,3) (1,0) 등 홀수 자리가
          //  black 라면, 좌측 상단이 백색으로 시작하는 것이고
          if (board[k][l] === "B") {
            typeA++;
          } 
 		  // (0,0) (0,2) (1,1) 등 짝수 자리가
          //  white 라면, 좌측 상단이 흑색으로 시작하는 것이다.
          else {
            typeB++;
          }
        }
      }
    }
    if (minimum > typeA) minimum = typeA;
    if (minimum > typeB) minimum = typeB;
    // A 유형의 체스판에서 B 유형의 체스판 값이 올라 갔다는 것은
    // 내가 만들고자 하는 체스판과 다른 것 즉, 틀린 것이기 때문에
    // 결국 B는 유형과 다른 색깔의 개수를 의미한다.
  }
}
console.log(minimum);

 

* 효과적인 방법에 대한 설명이나 잘못된 부분에 대한 코멘트를 좋아합니다 :)

 댓글을 통해 여러분들의 생각을 남겨주세요!