[알고리즘] 백준 - 1018 체스판 다시 칠하기 해설, node js 구현

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

1018번: 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

해설

사실 부르트포스에 해설이랄게 뭐 있을까요? ㅠㅠ

하나하나 다 숫자를 세보면 됩니다!

 

저 같은 경우에는 첫번째 칸이 'B' 또는 'W'로 시작하고, 8x8 크기의 체스판을 칠할때

몇번을 칠하면 원하는 색으로 시작하는 체스판이 완성이 되는지

count하는 함수를 작성했어요.

 

countNeedPating(startRowNum, startColNum, startColor) 함수를 작성했고,

인수로 시작하는 row, col, color을 받아서 8x8을 직접 칠해보면서, count를 해줬습니다.

 

여기서 한가지 집중했던 점은

 

8x8 체스판은 64번을 칠하면 완성이 되는데,

첫번째 칸이 'B'일때와 'W'일때의 색칠해야 하는 횟수를 합치면 64가 된다는 것입니다.

따라서 B나 W로 시작하는 경우의 색칠 횟수 한번만 구하면 나머지 경우도 계산이 됩니다.

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
 
// input을 미리 정리합니다.
const [height, width] = input[0].split(' ').map(el => parseInt(el))
const originBoard = []
for(let i = 1; i <= height; i++) {
  let row = input[i].split('')
  originBoard.push(row)
}
 
// 우리가 색칠 할 Size를 먼저 정의를 해주었습니다.
// 문제를 풀때 x, y 만 수정하면 작은 경우의 수부터 테스트를 진행 할 수 있거든요.
const SIZE = {x:8, y:8}
 
// 색칠 횟수를 count 하는 함수를 먼저 정의합니다.
// 시작하는 위치에서 부터 SIZE에서 정의한 만큼의 체스판을 색칠해봅니다.
function countNeedPainting(startRowNum, startColNum, startColor) {
  let nextColor = startColor;
  let count = 0;
  // i = row
  for(let i = startRowNum; i < startRowNum + SIZE.x; i++) {
    // j = column
    for(let j = startColNum; j < startColNum + SIZE.y; j++) {
      if(originBoard[i][j] !== nextColor) {
        count++;
      }
      nextColor = nextColor === 'B' ? 'W' : 'B'
    }
    nextColor = nextColor === 'B' ? 'W' : 'B'
  }
  return count;
}
 
// 최소값을 미리 넉넉하게 설정해 뒀습니다.
let min = SIZE.x * SIZE.y;
// 전체 크기에서 체스판을 자를 수 있는 모든 경우의 수를 loop를 돌며 확인합니다.
for(let i = 0 ; i <= height - SIZE.x; i++) {
  for(let j = 0; j <= width - SIZE.y; j++) {
    const blakCount = countNeedPainting(i, j, 'B');
    const whiteCount = (SIZE.x * SIZE.y) - blakCount;
    const currentMin = blakCount > whiteCount ? whiteCount : blakCount
 
    if(min > currentMin) {
      min = currentMin
    }
  }
}
 
console.log(min)