[JavaSrcipt] Baekjoon - 1018 : 체스판 다시 칠하기

문제

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

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

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

입력

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

출력

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

 

예제입력	예제출력
	1
	12

 

 

❌ 풀이

무작정 전체검증을 하는 브루트포스 단계이긴하지만

이번문제는 어딘가에서 생각이 멈춰버렸다.

for문을 사용해 n,m의 -8까지를 8*8체스판크기를 자를 시작점으로 하려했으나

그 다음에 시작점부터 +8만큼을 가야하는데 어떻게 구현해야하나 감이안잡혔다.

 

이 무작위의 사각형에서 8*8판을 위해 -8까지의 시작점과 +8만큼의 끝점을 구현했다해도

W,B여부를 확인해 조건문을 설정하는 부분에서 막혔을것같다.

 

그래서 다른분의풀이를 참고하며 이해해보도록했다.

 

✅ 다른분의 풀이

const input=require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const size=input.shift();
let [n,m]=size.split(' ').map(o=>Number(o));

const chess=['WBWBWBWB','BWBWBWBW'];
let min=64;

for(let i=0;i<=n-8;i++){
    for(let j=0;j<=m-8;j++){
        for(let oe=0;oe<2;oe++){
            let count=0;
            for(let x=i;x<i+8;x++){
                for(let y=j;y<j+8;y++){
                    if(input[x][y]!=chess[(x+oe)%2][y-j]){count++}
                }
            }
            if(count<min){min=count}
        }
    }
}
console.log(min);

우선 미리 [ 'WBWBWBWB' , 'BWBWBWBW' ] 의 chess배열을 선언해준다.

 

그리고 생각했던것처럼 n,m의 -8까지가 8*8을 자르는 시작점으로 정해주셨다.

여기서 for문을 더 깊게 들어가야했던것이다.

 

❗ 즉 [i][j]는 

마지막 노란색B까지만 하면 제일 우측하단 즉 주어진 보드의 끝까지 체크할 수 있으니까

노란색범위까지만 제공을 하는것이다.

 

그럼이제 저 해당 시작점에서 8*8칸만큼을 검증해야한다.

이를 구현하기위해 

x=i를 받고 x<i+8까지 반복하는 for문을

y=j를 받고 y<j+8까지 반복하는 for문을 적었다.

 

예를들어 i가 2이고 j가 1이었다면 [2][1]부터 [9][8]까지 검증을하게된다.

if(input[x][y]!=chess[(x+oe)%2][y-j]){count++}

이때 조건문이 [x][y]와 미리만들어둔 chess배열을 비교하는데

oe 는 odds and evens 를 줄여쓴것으로 홀,짝을 의미한다.

 

oe는 0,

[x][y]가 [3][2]라고 가정한다면

chess[(3+0)%2][2-0]

지민이가 획득한 보드판의 [3][2]와

만들어준 정돈된 체스판의[1][2]와 비교한다.

 

if문의 chess[(x+oe)%2][y-j]) 에서 [(x+oe)%2]는 

다시말해 1과 0만 홀,짝만 반복된다는것이다.

 

그리고 x,y를 사용하는 for문 바깥에는

oe를 사용하는 for문이 있는데

이는 잘려질 체스판이 B부터 시작해야 다시칠할 사각형이 더 적은지

W부터 시작해야 더 적은지 모르기때문이다.

 

이것또한 예를들면

옳게된 체스판8*8짜리에 가운데 하나만 틀려있는 예제1번이라면

지민이가 획득한 보드판의 첫줄은 WBWBWBWB인데

[(x+oe)%2]의 값이 0이고 만들어둔 옳게된 chess배열이 [ 'BWBWBWBW' , 'WBWBWBWB' ]라면

보드판과 WBWBWBWB와 옳게된배열 BWBWBWBW를 비교해 64사각형을 다 반복하면

count는 63까지 올라갈것이다.

 

min=64 보다 적으니 min=count에의해 63이들어가겠지만 이는 답이아니다.

그러므로 oe를 사용한 반복문에서 oe++를하여

[(x+oe)%2]의 값이 1이된다면 

WBWBWBWB와 WBWBWBWB를 비교해 64사각형을 다 반복하면

count는 1까지만 올라가게된다.

 

W로 시작하던 B로 시작하던 상관없이

두 경우를 다 비교해서 더 적은횟수를 가져가게된다.

 

 

 

아직 어떻게 구현해야하나 어디까지 들어가 반복해야하나 등

다른분들의 코드를 보며 겨우이해하는게 전부일정도로

떠올려지지않는게 너무많다.

 

 

-출처

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