[백준]1018번: 체스판 다시 칠하기 문제풀이(자바/JAVA)

안녕하세요!

 

백준 단계별로 풀어보기 12단계, 브루트 포스에 위치한 체스판 다시 칠하기 문제를 풀어봤습니다.

 

1018번 문제의 링크입니다.

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는 흰색이다.

출력

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

 

 

문제를 처음 보고나서,, 모든 경우의 수를 세지 않고 풀 수 있는 방법이 있지 않을까? 생각하다가 테마가 브루트 포스이기도 하고, 모든 경우의 수를 다 세는 방법밖에 없다고 생각했습니다.. 

 

해결책은 다음과 같습니다. 입력값의 N과 M이 8보다 크거나 같고 8X8크기의 체스판을 만드는 것이기 때문에 기준시작점을 아래 그림과 같이 잡고 8X8크기의 정사각형으로 모든 경우의 수를 세는 방법입니다. 

인덱스번호0,0일때 기준시작점

 

인덱스번호0,1일때 기준시작점

 

이와 같이, 기준점과 8X8의 틀을 잡은 후 모든 경우의 수를 계산합니다. 이때 핵심은 계산할때 올바른 답안이 2개가나올 수 있다는 점입니다. WBWBWBWB 순으로 가야하는 경우, BWBWBWBW순으로 가야하는 경우 중 최소한의 count를 계산해야 합니다. 자바코드를 통해 알아보겠습니다.

 

 

먼저 첫번째 for문에서는 입력값을 받은후 배열에 W면 true, B면 false를 대입했습니다. 

 

두번째 4개의 for문에서는 주요로직이 실행되는 부분입니다. 전체 8x8의 틀이 움직이는 부분이 첫번째와 두번째 for문입니다. 입력받은 세로와 가로 인덱스번호에서 7을 빼주는데, 예를 들어 11 12의 사각형이라면 11에서 7을 빼주고 12에서 7을빼주는 것입니다. 그 이유는 7을빼줘야 0, 1, 2, 3의 for문이 도는데, 총 8x8의 틀이 세로로 4번움직여야 하기 때문입니다. 가로도 마찬가지입니다. 세번째와 네번째의 for문은 8x8틀안에서 count를 계산하는 로직입니다. temp를 이용해 비교하고 매번 비교시마다 temp 값을 바꾸고 줄이바뀔때마다 temp값을 바꿨습니다. 매번 비교시마다 바꾸는 이유는, 정답은 WBWBWBWB이거나 BWBWBWBW 둘중에 하나이기때문이고 줄이바뀔때마다는 8번째(인덱스번호7)가 그대로 아랫줄 첫번째(인덱스번호0)이기 때문입니다.

 

그 후, 최소값을 계산해 count변수에 대입했는데, 두개중에 최소값을 계산한이유는, 정답이 기준점을 기준으로 2개이기 때문입니다. 이후 최대 count경우의 수인 63번을 바꾸는 경우와 계산된 count의 최소값을 구해 정답을 찾았습니다.

 

문제를 풀다보며 느낀점은, 알고리즘 자체는 쉬웠지만 for문의 번호를 대입하는게 헷갈렸습니다.  많은 경험과 노하우가 필요함을 알 수 있었습니다!