[알고리즘/javascript] 백준 1018번: 체스판 다시 칠하기

✏️ Problem

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

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

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

 

🧑‍💻 Solution

[ 작성한 코드 ]

const [size, ...arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [row, col] = size.split(' ').map(Number);
const board = arr.map(ele => ele.split(''));
const answer = [];

// 체스판이 흰색으로 시작하는 경우와 검은색으로 시작하는 경우를 미리 선언
const white = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']
const black = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']

// 흰색으로 먼저 시작하는 경우라 가정하여 비교
function whiteFirstBoard(x, y) {
    let cnt = 0;
    
    for(let i = 0; i < 8; i++) {
        for(let j = 0; j < 8; j++) {
            if(board[i + x][j + y] !== white[i][j]) cnt++;
        }
    }
    return cnt;
}

// 검은색으로 먼저 시작하는 경우라 가정하여 비교
function blackFirstBoard(x, y) {
    let cnt = 0;
    
    for(let i = 0; i < 8; i++) {
        for(let j = 0; j < 8; j++) {
            if(board[i + x][j + y] !== black[i][j]) cnt++;
        }
    }
    return cnt;
}

// 보드판을 돌면서 8x8의 체스판을 만들어 두 가지 경우를 모두 탐색한다.
for(let i = 0; i < row-7; i++) {
    for(let j = 0; j < col-7; j++) {
        answer.push(whiteFirstBoard(i, j));
        answer.push(blackFirstBoard(i, j));
    }
}

// 결과 출력 (모든 경우의 수 중 가장 작은 값을 찾는다)
console.log(Math.min(...answer));

 

[ 설계 ]

첫 번째 시도에서는 오른쪽 + 아래에 있는 요소가 나랑 같을 경우 count를 올리는 식으로 코드를 작성했다.

그럴 경우에는 검은색이 먼저 시작하는지, 흰색이 먼저 시작하는 지를 고려할 수 없기 때문에

아래 예제 입력4의 경우에서 답이 달라지게 된다.

예제 4에서는 어디에서 시작해도 B로 시작하기 때문에 오른쪽 요소와 아래 요소가 W로 바뀌게 되고 그렇게 된다면 오른쪽 가장 아래에 있는 W는 B로 바뀌게 되어 답이 31이 아닌 32가 나온다. 다른 경우를 생각해야 한다.

 

문제의 핵심은 검은색으로 시작하는 경우와 흰색으로 시작하는 경우를 모두 고려해야 한다는 것이다.

white, black 변수에 흰색으로 시작하는 경우(8x8)과 검은색으로 시작하는 경우(8x8)을 미리 선언해둔다.

그리고 보드판에서 8x8로 자르면서 미리 만들어둔 white와 black과 비교한다.

 

비교는 아래와 같이 두 번 실행해야 한다.

1. 왼쪽 첫 번째 요소가 흰색인 경우
2. 왼쪽 첫 번째 요소가 검은색인 경우

비교를 실행하면서 이동 횟수를 모두 answer 배열에 넣어두고 마지막으로 answer에서의 최소값을 출력하면 된다.