문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
구상
우선 2차원 배열로 입력값 받아오기. 그리고 반복문을 통해 검사해야겠지? 반복문을 통해 체스 구성을 하나씩 받아올 때
black이 몇개인지, white가 몇개인지 세줘야겠다. 근데, 행,열 위치에 따라 체스판의 경우가 두가지가 있으니까 black배열과 white배열을 만들어서 행열위치에 따라 다르게 카운트 해줘야지 !
코드
#include <iostream>
using namespace std;
int main()
{
int n,m;
cin >> n >> m;
char chess[n][m];
int count[n-7][m-7];
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
cin >> chess[i][j];
}
}
for (int i=0; i<n-7; i++){
for (int j=0; j<m-7; j++){
int black[2]={0,0};
int white[2]={0,0};
for (int k=i; k<i+8; k++){
for (int l=j; l<j+8; l++){
if ((l%2==0 && k%2==0) || (l%2==1 && k%2==1)){
if (chess[k][l] == 'B') black[0]++;
else if (chess[k][l] == 'W') white[0]++;
}
else if ((l%2==1 && k%2==0) || (l%2==0 && k%2==1)){
if (chess[k][l] == 'B') black[1]++;
else if (chess[k][l] == 'W') white[1]++;
}
}
}
if (black[0]+white[1]>black[1]+white[0]) count[i][j] = black[1]+white[0];
else count[i][j] = black[0]+white[1];
}
}
int min = count[0][0];
for (int i=0; i<n-7; i++){
for (int j=0; j<m-7; j++){
if (min>count[i][j]) min = count[i][j];
}
}
cout << min;
return 0;
}
코드 설명
1. 바깥 이중 for문 (i,j)
먼저 맨 바깥 이중 포문 (i,j)는 8*8을 보기위한 반복문이다. 그래서 범위는, 8*8을 검사하기때문에 n-7, m-7로 제한한다. (ex. 15*15의 체스판이 들어올 경우, 8*8체스판은 7*7=49개) 안의 이중 포문 (k,l)을 통해 8*8체스판의 B,W를 알맞게 카운트 해줬다면, black[0] , white[1]을 더했을 때와 black[1], white[0]을 더했을 때 대소비교를 해주어서, 더 작은 쪽을 count배열에 넣어준다. 왜냐하면 더했을 때 더 크다는 뜻은, 배치가 제대로 된 칸들이 많다는 뜻이고, 그럼 더 작은 쪽은 수정을 해야되는 칸들이기때문이다.
2. 내부 이중 for문 (k,l)
안의 이중 for문은 8*8체스판에 B,W가 어떻게 채워져있는지 세준다. 이때, 체스판은 두가지 경우가 있다고 했다. 맨 왼쪽 위 칸이 검정색인경우, 흰색인 경우이다. 그리고, 체스판은 번갈아가면서 채워지기 때문에 B는 두칸 간격으로 나온다.
맨 왼쪽 위칸은 행%2==0, 열%2==0이다. 위로도, 아래로도 두칸 간격으로 패턴이 나타나기때문에, 정상적인 체스판이라면 행%2==0, 열%2==0인 칸들은 모두 같은 색이 나타날것이다. 또한 격자무늬이므로 행%1==0, 열%2==0또한 행%2==0, 열%2==0과 같은 색일것이다. 이러한 성질을 이용해서 B와 W가 얼마나 제대로 들어가있는지 세주었다.
3. 마지막 for문
count배열에는 체스판의 모든 8*8 을 확인해서 수정해야되는 칸의 수가 들어있다. 그래서 for문을 통해 count배열을 다 훑어서, 제일 작은 수(제일 수정 적게 하는 체스판)을 출력한다.
시행착오
실은 문제 이해를 잘못했다.. 체스판이 입력되면 8*8을 자르기 제일 좋은 곳을 찾아서 그 중 수정된 개수를 출력하는 것이 요구사항이었는데, 난 그냥 입력된 체스판이 최소 몇개를 고쳐야 완전한 체스판이 되는지를 출력하는 것인 줄 알았다. 그래서 그렇게 코드를 짜고 디버깅을 해보고.. 했고 기록도 남겼는데 이게 아니었던 것을 알고 왕 화나서 그냥 기록을 다 날려버렸다.. 다행히 조금의 수정만 가하니 원하는 요구사항을 출력할 수 있었다.
설명을 아주아주 못하는 편이라.... 그리고 이런 코드 블로그는 처음이라...... 설명도 못하고 설명을 뒷받침하는 자료도, 디버깅 기록도 없어서 난해한 포스팅이 된 거 같다. 다음 포스팅부턴 조금 더 신경써야될 것 같다 ㅜㅜ